建议用标题旁边打开的目录，更清晰明了！
太多了，编辑的时候要找好久，数据结构和图论都搬出去了，下面有链接。离数学搬家也不远了。
其他
读入、输出优化（必加！！！）
快读
模板
inline int read(){int sum=0,f=1;char a=getchar();while(a<'0' || a>'9'){if(a=='-') f=-1;a=getchar();}while(a>='0' && a<='9') sum=sum*10+a-'0',a=getchar();return sum*f;
}
快输
模板
void print(int x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');
}
数据结构
图论
字符串
AC 自动机
模板指路
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi firstconst int N=2e6+5;
struct node{int end,fail,s[26];
};
node a[N];
int n,co;void insert(string s){int u=0;for(int i=0;i<s.size();++i){if(!a[u].s[s[i]-'a']) a[u].s[s[i]-'a']=++co;u=a[u].s[s[i]-'a'];}a[u].end++;
}
void get_fail(){queue<int> q;for(int i=0;i<26;++i)if(a[0].s[i])q.push(a[0].s[i]),a[a[0].s[i]].fail=0;while(q.size()){int x=q.front();q.pop();for(int i=0;i<26;++i){if(a[x].s[i])a[a[x].s[i]].fail=a[a[x].fail].s[i],q.push(a[x].s[i]);else a[x].s[i]=a[a[x].fail].s[i];}}
}
int fi(string s){int res=0,u=0;for(int i=0;i<s.size();++i){u=a[u].s[s[i]-'a'];for(int j=u;j && a[j].end!=-1;j=a[j].fail)res+=a[j].end,a[j].end=-1;}return res;
}int main(){cin>>n;for(int i=1;i<=n;++i){string s;cin>>s;insert(s);}get_fail();string s;cin>>s;printf("%d",fi(s));return 0;
}
数学
大小步（BSGS）
点击查看代码
int bsgs(int a,int b,int p){//(a^x)%p=b%p map<int,int> ha;int t=sqrt(p)+1;for(int i=0,q=b%p;i<t;++i,q=q*a%p) ha[q]=i;int w=ksm(a,t,p);for(int i=1,q=w;i<=t;++i,q=q*w%p)if(ha.find(q)!=ha.end()) return t*i-ha[q];return -1;
}
拓展欧几里得定理（exgcd）
点击查看代码
int exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return a;}int g=exgcd(b,a%b,x,y),t=x;x=y,y=t-a/b*y;return g;
}
中国剩余定理（CRT）
点击查看代码
int CRT(){int m=1,res=0,x,y;for(int i=1;i<=n;++i) m*=a[i];for(int i=1;i<=n;++i){int tmp=m/a[i];exgcd(tmp,a[i],x,y);res=(res+tmp*x*b[i]%m)%m;}return (res%m+m)%m;
}
线性筛法求欧拉函数
点击查看代码
void init(int n){for(int i=2;i<=n;++i){if(!vi[i]) pr[++co]=i,phi[i]=i-1;for(int j=1;j<=co && i*pr[j]<=n;++j){vi[pr[j]*i]=1;if(i%pr[j]==0){phi[pr[j]*i]=phi[i]*pr[j];break;}else phi[i*pr[j]]=phi[i]*(pr[j]-1);}}
}
基础算法
快速幂
点击查看代码
int ksm(int x,int y){int res=1;while(y){if(y&1) res=(res*x)%p;y>>=1,x=(x*x)%p;}return res%p;
}
