常用模板总结

快读快写

d0j1a_1701/适用于C++11以上的快速IO

高精度

From Baobaobear/MiniBigInteger

#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>

struct BigInt{int sign;std::vector<int>v;BigInt():sign(1){}BigInt(const std::string&s){*this=s;}BigInt(int v){char buf[21];sprintf(buf,"%d",v);*this=buf;}void zip(int unzip){if(unzip==0){for(int i=0;i<(int)v.size();i++)v[i]=get_pos(i*4)+get_pos(i*4+1)*10+get_pos(i*4+2)*100+get_pos(i*4+3)*1000;}else for(int i=(v.resize(v.size()*4),(int)v.size()-1),a;i>=0;i--)a=(i%4>=2)?v[i/4]/100:v[i/4]%100,v[i]=(i&1)?a/10:a%10;setsign(1,1);}int get_pos(unsigned pos)const{return pos>=v.size()?0:v[pos];}BigInt&setsign(int newsign,int rev){for(int i=(int)v.size()-1;i>0&&v[i]==0;i--)v.erase(v.begin()+i);sign=(v.size()==0||(v.size()==1&&v[0]==0))?1:(rev?newsign*sign:newsign);return*this;}std::string to_str()const{BigInt b=*this;std::string s;for(int i=(b.zip(1),0);i<(int)b.v.size();++i)s+=char(*(b.v.rbegin()+i)+'0');return(sign<0?"-":"")+(s.empty()?std::string("0"):s);}bool absless(const BigInt&b)const{if(v.size()!=b.v.size())return v.size()<b.v.size();for(int i=(int)v.size()-1;i>=0;i--)if(v[i]!=b.v[i])return v[i]<b.v[i];return false;}BigInt operator-()const{BigInt c=*this;c.sign=(v.size()>1||v[0])?-c.sign:1;return c;}BigInt&operator=(const std::string&s){if(s[0]=='-')*this=s.substr(1);else{for(int i=(v.clear(),0);i<(int)s.size();++i)v.push_back(*(s.rbegin()+i)-'0');zip(0);}return setsign(s[0]=='-'?-1:1,sign=1);}bool operator<(const BigInt&b)const{return sign!=b.sign?sign<b.sign:(sign==1?absless(b):b.absless(*this));}bool operator==(const BigInt&b)const{return v==b.v&&sign==b.sign;}BigInt&operator+=(const BigInt&b){if(sign!=b.sign)return*this=(*this)- -b;v.resize(std::max(v.size(),b.v.size())+1);for(int i=0,carry=0;i<(int)b.v.size()||carry;i++){carry+=v[i]+b.get_pos(i);v[i]=carry%10000,carry/=10000;}return setsign(sign,0);}BigInt operator+(const BigInt&b)const{BigInt c=*this;return c+=b;}void add_mul(const BigInt&b,int mul){v.resize(std::max(v.size(),b.v.size())+2);for(int i=0,carry=0;i<(int)b.v.size()||carry;i++){carry+=v[i]+b.get_pos(i)*mul;v[i]=carry%10000,carry/=10000;}}BigInt operator-(const BigInt&b)const{if(sign!=b.sign)return(*this)+-b;if(absless(b))return-(b-*this);BigInt c;for(int i=0,borrow=0;i<(int)v.size();i++){borrow+=v[i]-b.get_pos(i);c.v.push_back(borrow);c.v.back()-=10000*(borrow>>=31);}return c.setsign(sign,0);}BigInt operator*(const BigInt&b)const{if(b<*this)return b**this;BigInt c,d=b;for(int i=0;i<(int)v.size();i++,d.v.insert(d.v.begin(),0))c.add_mul(d,v[i]);return c.setsign(sign*b.sign,0);}BigInt operator/(const BigInt&b)const{BigInt c,d;d.v.resize(v.size());double db=1.0/(b.v.back()+(b.get_pos((unsigned)b.v.size()-2)/1e4)+(b.get_pos((unsigned)b.v.size()-3)+1)/1e8);for(int i=(int)v.size()-1;i>=0;i--){c.v.insert(c.v.begin(),v[i]);int m=(int)((c.get_pos((int)b.v.size())*10000+c.get_pos((int)b.v.size()-1))*db);c=c-b*m,d.v[i]+=m;while(!(c<b))c=c-b,d.v[i]+=1;}return d.setsign(sign*b.sign,0);}BigInt operator%(const BigInt&b)const{return*this-*this/b*b;}bool operator>(const BigInt&b)const{return b<*this;}bool operator<=(const BigInt&b)const{return!(b<*this);}bool operator>=(const BigInt&b)const{return!(*this<b);}bool operator!=(const BigInt&b)const{return!(*this==b);}};

矩阵

template<typename Tp,Tp mod>struct Matrix{vector<vector<Tp>>arr;int row,col;Matrix()=default;inline Matrix(int r,int c){arr.resize(r+1);for(auto&vec:arr)vec.resize(c+1);row=r,col=c;}inline void clear(){for(auto&vec:arr)vec.clear();arr.clear();row=col=0;}inline void resize(int r,int c){arr.resize(r+1);for(auto&vec:arr)vec.resize(c+1);row=r,col=c;}inline static Matrix<Tp,mod>unit(int squ){Matrix<Tp,mod>res(squ,squ);for(int i=1;i<=squ;i++)res.arr[i][i]=1;return res;}inline vector<Tp>&operator[](const int&pos){return arr[pos];}inline Matrix<Tp,mod>operator+(const Matrix&m)const{Matrix<Tp,mod>res(row,col);for(int i=1;i<=row;i++)for(int j=1;j<=col;j++)res.arr[i][j]=(arr[i][j]+m.arr[i][j])%mod;return res;}inline Matrix<Tp,mod>operator-(const Matrix m)const{Matrix<Tp,mod>res(row,col);for(int i=1;i<=row;i++)for(int j=1;j<=col;j++)res.arr[i][j]=(arr[i][j]-m.arr[i][j])%mod;return res;}inline Matrix<Tp,mod>operator*(const Matrix m)const{Matrix<Tp,mod>res(row,m.col);for(int i=1;i<=row;i++)for(int k=1;k<=col;k++)for(int j=1;j<=m.col;j++)res.arr[i][j]+=(arr[i][k]*m.arr[k][j])%mod,res.arr[i][j]%=mod;return res;}inline Matrix<Tp,mod>operator^(long long power){Matrix<Tp,mod>res=unit(row);do{if(power&1)res=res**this;*this=*this**this;power>>=1;}while(power);return res;}};