呼，终于在考试之前复习了一遍所有模板。

球NOIP不跪！

BigNumber

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7 const int maxlen=3100;  8 struct bigint  9 { 10     int a[maxlen],len; 11     bigint() 12     { 13         memset(a,0,sizeof a); 14         len=1; 15     } 16     bigint(string str) 17     { 18         memset(a,0,sizeof a); 19         len=str.length(); 20         for(int i=1;i<=len;i++)a[i]=str[len-i]-'0'; 21     } 22     bigint(int num) 23     { 24         memset(a,0,sizeof a); 25         len=0; 26         if(num==0)len++; 27         else while(num)a[++len]=num%10,num/=10; 28     } 29     string tostring() 30     { 31         string str; 32         for(int i=len;i;i--)str+=char(a[i]+'0'); 33         return str; 34     } 35     inline int& operator[](int num){
   return a[num];} 36     friend bool operator<(bigint& a,bigint& b) 37     { 38         if(a.len>b.len)return false; 39         if(a.len
          
           b[i])return false; 43 if(a[i]
           
            (bigint& a,bigint& b){ return b
            
             =(bigint& a,bigint& b){ return !(a
             
              b);} 56 friend bigint operator+(bigint& a,bigint& b) 57 { 58 bigint c;c.len=max(a.len,b.len); 59 for(int i=1;i<=c.len;i++)c[i]=a[i]+b[i]; 60 for(int i=1;i<=c.len;i++) 61 if(c[i]>=10)c[i]-=10,c[i+1]++; 62 while(c[c.len+1]) 63 { 64 c.len++; 65 if(c[c.len]>=10)c[c.len]-=10,c[c.len+1]++; 66 } 67 return c; 68 } 69 friend bigint& operator+=(bigint& a,bigint& b){ return a=a+b;} 70 friend bigint operator-(bigint& a,bigint& b) 71 { 72 bigint c;c.len=a.len; 73 for(int i=1;i<=c.len;i++)c[i]=a[i]-b[i]; 74 for(int i=1;i<=c.len;i++) 75 if(c[i]<0)c[i]+=10,c[i+1]--; 76 while(c.len&&!c[c.len])c.len--; 77 if(!c.len)c.len=1; 78 return c; 79 } 80 friend bigint& operator-=(bigint& a,bigint& b){ return a=a-b;} 81 friend bigint operator*(bigint& a,int b) 82 { 83 bigint c;c.len=a.len; 84 for(int i=1;i<=c.len;i++)c[i]=a[i]*b; 85 for(int i=1;i<=c.len;i++)c[i+1]+=c[i]/10,c[i]%=10; 86 while(c[c.len+1])c.len++,c[c.len+1]+=c[c.len]/10,c[c.len]%=10; 87 return c; 88 } 89 friend bigint operator*(int b,bigint& a){ return a*b;} 90 friend bigint operator*=(bigint& a,int b){a=a*b;return a;} 91 friend bigint operator*(bigint a,bigint b) 92 { 93 bigint c;c.len=a.len+b.len-1; 94 for(int i=1;i<=a.len;i++) 95 for(int j=1;j<=b.len;j++) 96 c[i+j-1]+=a[i]*b[j]; 97 for(int i=1;i<=c.len;i++)c[i+1]+=c[i]/10,c[i]%=10; 98 while(c[c.len+1])c.len++,c[c.len+1]+=c[c.len]/10,c[c.len]%=10; 99 return c;100 }101 friend bigint operator*=(bigint& a,bigint b){a=a*b;return a;}102 friend bigint operator/(bigint& a,int b)103 {104 bigint c;c.len=a.len;105 int d=0;106 for(int i=a.len;i;i--)d=d*10+a[i],c[i]+=d/b,d%=b;107 while(c.len&&!c[c.len])c.len--;108 if(!c.len)c.len=1;109 return c;110 }111 friend int operator%(bigint& a,int b)112 {113 int d=0;114 for(int i=a.len;i;i--)d=(d*10+a[i])%b;115 return d;116 }117 friend bigint operator/(bigint& a,bigint& b)118 {119 bigint c,d;c.len=a.len;120 for(int i=a.len;i;i--)121 {122 d*=10;d[1]+=a[i];123 while(d>=b)d-=b,c[i]++;124 }125 while(c.len&&!c[c.len])c.len--;126 if(!c.len)c.len=1;127 return c;128 }129 friend bigint operator%(bigint& a,bigint& b)130 {131 bigint d;132 for(int i=a.len;i;i--)133 {134 d*=10;d[1]+=a[i];135 while(d>=b)d-=b;136 }137 return d;138 }139 140 };141 void div(bigint& a,int b,bigint& p,int &c)142 {143 memset(p.a,0,sizeof p.a);p.len=a.len;c=0;144 for(int i=a.len;i;i--)145 {146 c=c*10+a[i];147 p[i]+=c/b;148 c%=b;149 }150 while(p.len&&!p[p.len])p.len--;151 if(!p.len)p.len=1;152 }153 bigint gcd(bigint a,bigint b)154 {155 while(!(b.len==1&&b[1]==0))a=a%b,swap(a,b);156 return a;157 }158 int main(int argc, char *argv[])159 {160 161 return 0;162 }
             
            
           
          
         
        
       
      
     

SuffixArray

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int maxlen=310000; 8 inline int change(char ch){
   return ch-'a';} 9 int rank[maxlen],sa[maxlen];10 int trank[maxlen],tsa[maxlen];11 int isort[maxlen];12 int height[maxlen];13 void suffix_array(string str)14 {15     int len=str.length();str="&"+str;16     for(int i=1;i<=len;i++)isort[change(str[i])]++;17     for(int i=change('a')+1;i<=change('z');i++)isort[i]+=isort[i-1];18     for(int i=len;i;i--)sa[isort[change(str[i])]--]=i;19     for(int i=1;i<=len;i++)rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);20     for(int o=1;o<=2*len;o*=2)21     {22         for(int i=1;i<=len;i++)isort[i]=0;23         for(int i=1;i<=len;i++)isort[rank[i+o]]++;24         for(int i=1;i<=len;i++)isort[i]+=isort[i-1];25         for(int i=len;i;i--)tsa[isort[rank[i+o]]--]=i;26         for(int i=1;i<=len;i++)isort[i]=0;27         for(int i=1;i<=len;i++)isort[rank[i]]++;28         for(int i=1;i<=len;i++)isort[i]+=isort[i-1];29         for(int i=len;i;i--)sa[isort[rank[tsa[i]]]--]=tsa[i];30         for(int i=1;i<=len;i++)trank[sa[i]]=trank[sa[i-1]]31                 +(rank[sa[i]]>rank[sa[i-1]]||rank[sa[i]+o]>rank[sa[i-1]+o]);32         for(int i=1;i<=len;i++)rank[i]=trank[i];33     }34     for(int i=1;i<=len;i++)35         if(rank[i]!=len)36         {37             while(str[i+height[rank[i]]]==str[sa[rank[i]+1]+height[rank[i]]])height[rank[i]]++;38             height[rank[i+1]]=max(height[rank[i]]-1,0);39         }40 }41 int main(int argc, char *argv[])42 {43     44     return 0;45 }
         
        
       
      
     

Aho-Corasick automaton

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 inline int change(char ch) 8 { 9     if(ch=='A')return 0;10     if(ch=='T')return 1;11     if(ch=='G')return 2;12     if(ch=='C')return 3;13 }14 struct node{
   int s[4],fail;bool isend;}t[2100];int tnum;15 void add(string str)16 {17     int now=0;18     for(int i=0;i
         
        
       
      
     

Dinic

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int maxpoint=110000,maxedge=1100000,inf=2147483647; 7 int head[maxpoint],nowhead[maxpoint],pointsize; 8 struct edge{
   int to,next,c;}g[maxedge];int gnum=1; 9 void addedge(int from,int to,int c)10 {11     g[++gnum].to=to;g[gnum].c=c;g[gnum].next=head[from];head[from]=gnum;12     g[++gnum].to=from;g[gnum].c=0;g[gnum].next=head[to];head[to]=gnum;13 }14 int dfsstart,dfsend;15 int d[maxpoint];16 int q[maxpoint],ql,qr;17 bool BFS()18 {19     for(int i=1;i<=pointsize;i++)d[i]=0,nowhead[i]=head[i];20     q[ql=qr=1]=dfsend;21     while(ql<=qr)22         for(int now=q[ql++],i=head[now];i;i=g[i].next)23             if(g[i^1].c&&g[i].to!=dfsend&&!d[g[i].to])24                 d[q[++qr]=g[i].to]=d[now]+1;25     return d[dfsstart];26 }27 int DFS(int po,int delta)28 {29     if(po==dfsend)return delta;30     int nowans=0,t;31     for(int&i=nowhead[po];i&δi=g[i].next)32         if(g[i].c&&d[g[i].to]+1==d[po]&&(t=DFS(g[i].to,min(delta,g[i].c))))33             g[i].c-=t,g[i^1].c+=t,delta-=t,nowans+=t;34     return nowans;35 }36 int dinic(int start,int end)37 {38     dfsstart=start,dfsend=end;39     int ans=0;40     while(BFS())ans+=DFS(start,inf);41     return ans;42 }43 int main(int argc, char *argv[])44 {45     46     return 0;47 }
        
       
      
     

MincostMaxflow-Dinic

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int maxpoint=110000,maxedge=1100000,inf=2147483647; 7 int head[maxpoint],pointsize; 8 struct edge{
   int to,next,c,p;}g[maxedge];int gnum=1; 9 void addedge(int from,int to,int c,int p)10 {11     g[++gnum].to=to;g[gnum].c=c;g[gnum].p=p;g[gnum].next=head[from];head[from]=gnum;12     g[++gnum].to=from;g[gnum].c=0;g[gnum].p=-p;g[gnum].next=head[to];head[to]=gnum;13 }14 int dfsstart,dfsend;15 int d[maxpoint];16 bool havevis[maxpoint],isin[maxpoint];17 const int maxq=(1<<18)-1;18 int q[maxq+1],ql,qr;19 inline int inc(int&num){
   int temp=num;num=(num+1)&maxq;return temp;}20 bool SPFA()21 {22     for(int i=1;i<=pointsize;i++)d[i]=inf;23     ql=qr=0;d[q[inc(qr)]=dfsstart]=0;isin[dfsstart]=true;24     while(ql!=qr)25     {26         int now=q[inc(ql)];27         for(int i=head[now];i;i=g[i].next)28             if(g[i].c&&d[g[i].to]>d[now]+g[i].p)29             {30                 d[g[i].to]=d[now]+g[i].p;31                 if(!isin[g[i].to])isin[q[inc(qr)]=g[i].to]=true;32             }33         isin[now]=false;34     }35     return d[dfsend]
        
       
      
     

NumberTheory

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 typedef long long LL; 8 namespace Online 9 {10     inline int getnextfactor(int num)11     {12         for(int i=2,sqrtnum=(int)sqrt(num);i<=sqrtnum;i++)13             if(num%i==0)return i;14         return num;15     }16     int phi(int num)17     {18         if(num<=1)return 0;19         int ans=num;20         while(num>1)21         {22             int q=getnextfactor(num);23             ans=ans/q*(q-1);24             while(num%q==0)num/=q;25         }26         return ans;27     }28     LL gcd(LL a,LL b){
   return b?gcd(b,a%b):a;}29     LL exgcd(LL a,LL b,LL&x,LL&y)30     {31         if(!b){x=1,y=0;return a;}32         else{LL g=exgcd(b,a%b,x,y),t=x;x=y;y=t-a/b*y;return g;}33     }34 }35 namespace Offline36 {37     const int maxsize=210000;38     int prime[maxsize],pnum;39     bool isprime[maxsize];40     int phi[maxsize];41     void getlist(int listsize)42     {43         for(int i=2;i<=listsize;i++)isprime[i]=true;44         for(int i=2;i<=listsize;i++)45         {46             if(isprime[i])phi[prime[++pnum]=i]=i-1;47             for(int j=1;j<=pnum&&i*prime[j]<=listsize;j++)48             {49                 isprime[i*prime[j]]=false;50                 if(i%prime[j]==0)51                 {52                     phi[i*prime[j]]=phi[i]*prime[j];53                     break;54                 }55                 phi[i*prime[j]]=phi[i]*phi[prime[j]];56             }57         }58     }59 }60 namespace Mod_equation61 {62     int n;63     LL a[21000],b[21000];64     //x=a (mod b);65     LL la,lb;66     void solve()67     {68         la=a[1];lb=b[1];69         for(int i=2;i<=n;i++)70         {71             LL na=a[i],nb=b[i];72             LL p,q,g=Online::exgcd(lb,nb,p,q),d=na-la;73             if(d%g)return ;74             LL t=nb/g;p=(p*d/g%t+t)%t;75             la+    =lb*p;lb=nb*lb/g;76         }77     }78 }79 int main(int argc, char *argv[])80 {81     82     return 0;83 }
         
        
       
      
     

Tarjan(强连通)

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int maxpoint=11000,maxedge=51000; 7 int n,m; 8 struct point{
   int head,dfn,low,wk,instack;}p[maxpoint]; 9 struct edge{
   int next,to;}g[maxedge];int gnum;10 void addedge(int from,int to)11 {12     g[++gnum].to=to;g[gnum].next=p[from].head;p[from].head=gnum;13 }14 struct block{
   int size;}b[maxpoint];int bnum;15 int dfsnum;16 int s[maxpoint],sr=0;17 void tarjan(int po)18 {19     p[po].dfn=p[po].low=++dfsnum;20     p[s[++sr]=po].instack=true;21     for(int i=p[po].head;i;i=g[i].next)22     {23         if(!p[g[i].to].dfn)24             tarjan(g[i].to),p[po].low=min(p[po].low,p[g[i].to].low);25         else if(p[g[i].to].instack)26             p[po].low=min(p[po].low,p[g[i].to].dfn);27     }28     if(p[po].dfn==p[po].low)29     {30         bnum++;31         while(s[sr]!=po)p[s[sr]].instack=false,b[p[s[sr--]].wk=bnum].size++;32         p[s[sr]].instack=false,b[p[s[sr--]].wk=bnum].size++;33     }34 }35 int main(int argc, char *argv[])36 {37     38     return 0;39 }
        
       
      
     

Link-Cut Tree

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;struct node{
   int s[2],f,ws,rev;}p[210000];inline void maintain(int po){}inline void setson(int f,int s,int ws){p[p[f].s[p[s].ws=ws]=s].f=f;}inline bool isroot(int po){
   return (!p[po].f)||(p[p[po].f].s[0]!=po&&p[p[po].f].s[1]!=po);}inline void rotate(int po,int ws){    int son=p[po].s[ws];    if(isroot(po))p[son].f=p[po].f;    else setson(p[po].f,son,p[po].ws);    setson(po,p[son].s[!ws],ws);    setson(son,po,!ws);    maintain(po);maintain(son);}inline void reverse(int po){    if(p[po].rev)    {        swap(p[po].s[0],p[po].s[1]);        p[p[po].s[0]].ws^=1,p[p[po].s[1]].ws^=1;        p[p[po].s[0]].rev^=1,p[p[po].s[1]].rev^=1;        p[po].rev^=1;    }}inline int splay(int po){    while(!isroot(po))    {        int fa=p[po].f,gf=p[fa].f;        reverse(gf);reverse(fa);reverse(po);        if(isroot(fa)){rotate(fa,p[po].ws);break;}        if(p[po].ws==p[fa].ws)rotate(gf,p[fa].ws);        rotate(fa,p[po].ws);    }    reverse(po);maintain(po);    return po;}inline void access(int po){    for(int last=0;po;last=po,po=p[po].f)        splay(po),setson(po,last,1),maintain(po);}inline void makeroot(int po){access(po);splay(po);p[po].rev^=1;}inline void link(int u,int v){makeroot(u);p[u].f=v;}inline void cut(int u,int v){makeroot(u);access(u);splay(v);p[v].f=0;}int main(int argc, char *argv[]){        return 0;}