菜鸡的模板库。。。有些代码没跑过（?），所以如果有错，请大佬们指出，蒟蒻会虚心接受的2333
我是一条分割线（我也不知道为什么有一条分割线）
数论
BSGS以及扩展BSGS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//BSGS
map<int,int>Hash;
int BSGS(int x,int y){
x%=P,y%=P;
if(y==1)return 0;
if(!x&&!y)return 1;
if(!x)return -1;
Hash.clear();
int M=ceil(sqrt(P)),val=1,k=1;
for(int i=0;i<M;++i){
Hash[1ll*val*y%P]=i;
val=1ll*val*x%P;
}
for(int i=M;;i+=M){
k=1ll*k*val%P;
int T=(Hash.find(k)==Hash.end())?-1:Hash[k];
if(T!=-1)return i-T;
if(i>P)break;
}
return -1;
}
//扩展BSGS
ll exbsgs(ll A,ll B,ll P){
A%=P,B%=P;
if(B==1)return 0;
if(!A&&!B)return 1;
if(!A)return -1;
ll cnt=0,K=1,d;
while((d=gcd(A,P))!=1){
if(B%d)return -1;
cnt++;
B/=d,P/=d;
K=K*(A/d)%P;
if(B==K)return cnt;
}
ll M=ceil(sqrt(P));
Hash.clear();
ll val=1;
for(ll i=0;i<M;++i){
Hash[val*B%P]=i;
val=val*A%P;
}
for(ll i=M;;i+=M){
K=K*val%P;
int T=(Hash.find(K)==Hash.end())?-1:Hash[K];
if(T!=-1)return i-T+cnt;
if(i>P)break;
}
return -1;
}XXX变换(FFT&NTT&FWT)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//系统FFT
////原始
void FFT(complex<double>*T,int len,int ty){
complex<double>unit,mul,x,y;
int i,j,k,m;
for(i=0;i<len;++i){
for(j=0,k=i,m=len-1;m>0;j=(j<<1)|(k&1),k>>=1,m>>=1);
if(i<j)x=T[i],T[i]=T[j],T[j]=x;
}
for(m=1;m<len;m<<=1){
unit=exp(complex<double>(0,ty*pi/(double)(m)));
for(i=0;i<len;i+=(m<<1)){
mul=1;
for(j=0;j<m;++j){
x=T[i+j],y=T[i+j+m]*mul;
T[i+j]=x+y,T[i+j+m]=x-y;
mul*=unit;
}
}
}
if(ty==1)return;
for(int i=0;i<len;++i)T[i]=T[i]/len;
}
////优化
struct cpx{
double x,y;
cpx(){}
cpx(double xx, double yy){x=xx,y=yy;}
friend cpx operator *(cpx a,cpx b){return cpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
friend cpx operator /(cpx a,double b){return cpx(a.x/b,a.y/b);}
friend cpx operator +(cpx a,cpx b){return cpx(a.x+b.x,a.y+b.y);}
friend cpx operator -(cpx a,cpx b){return cpx(a.x-b.x,a.y-b.y);}
friend cpx operator *(cpx a,double b){return cpx(a.x*b,a.y*b);}
};
void BT(){
int len=N+M+1;
Len=1,L=0;
while(Len<len)Len<<=1,L++;
for(int i=0;i<Len;++i)rev[i]=(rev[i>>1]>>1|(i&1)<<(L-1));
}
void FFT(cpx *T,int len,int ty){
cpx unit,mul,x,y;
for(int i=0;i<len;++i)if(i<rev[i])swap(T[i],T[rev[i]]);
for(int m=1;m<len;m<<=1){
unit=cpx(cos(pi/m),ty*sin(pi/m));
for(int i=0;i<len;i+=(m<<1)){
mul=cpx(1,0);
for(int j=0;j<m;++j){
x=T[i+j],y=mul*T[i+j+m];
T[i+j]=x+y,T[i+j+m]=x-y;
mul=mul*unit;
}
}
}
if(ty==1)return;
for(int i=0;i<len;++i)T[i]=T[i]/len;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35//NTT
////原始
ll ksm(ll a,ll b){
ll ret=1;
while(b){
if(b&1)ret=ret*a%P;
a=a*a%P,b>>=1;
}
return ret;
}
void NTT(ll *T,int len,int ty){
int unit,mul,x,y;
int i,j,k,m;
for(i=0;i<len;++i){
for(j=0,k=i,m=len-1;m>0;j=(j<<1)|(k&1),k>>=1,m>>=1);
if(i<j)x=T[i],T[i]=T[j],T[j]=x;
}
for(m=1;m<len;m<<=1){
unit=ksm(G,(P-1+ty*(P-1)/(m<<1))%(P-1));
for(i=0;i<len;i+=(m<<1)){
mul=1;
for(j=0;j<m;++j){
x=T[i+j],y=T[i+j+m]*mul%P;
T[i+j]=(x+y)%P,T[i+j+m]=((x-y)%P+P)%P;
mul=mul*unit%P;
}
}
}
if(ty==1)return;
ll t=ksm(len,P-2);
for(int i=0;i<len;++i)T[i]=T[i]*t%P;
}
//拆系数NTT（找不到代码了）1
//FWT（到时候吧QAQ）
高斯消元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//高斯消元
void gauss(){
for(int i=1;i<=N;++i){
int x=i;
while(!Map[x][i]&&x<=N)x++;
if(x>N)return 0;
if(x!=i)for(int j=i;j<=N;++j)swap(Map[i][j],Map[x][j]);
int inv=ksm(Map[i][i],P-2);
for(int j=i+1;j<=N;++j){
if(!Map[j][i])continue;
int mul=Map[j][i]*inv%P;
for(int k=i;k<=N;++k)Map[j][k]=(Map[j][k]-Map[i][k]*mul%P+P)%P;
}
}
}行列式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//行列式
int gauss(){//去掉1行1列的余子式
int ans=1,cnt=0;
for(int i=2;i<=N;++i){
int x=i;
while(!Map[x][i]&&x<=N)x++;
if(x>N)return 0;
if(x!=i){
cnt^=1;
for(int j=i;j<=N;++j)swap(Map[i][j],Map[x][j]);
}
ans=ans*Map[i][i]%P;
int inv=ksm(Map[i][i],P-2);
for(int j=i+1;j<=N;++j){
if(!Map[j][i])continue;
int mul=Map[j][i]*inv%P;
for(int k=i;k<=N;++k)Map[j][k]=(Map[j][k]-Map[i][k]*mul%P+P)%P;
}
}
if(cnt)ans=(P-ans)%P;
return ans;
}线性基
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17//线性基
struct LB{
ll v[65];
void add(ll x){
for(int i=61;i>=0;--i){
if(x&(1ll<<i)){
if(!v[i]){v[i]=x;break;}
x^=v[i];
}
}
}
ll getmax(){
ll ret=0;
for(int i=61;i>=0;--i)ret=max(ret,ret^v[i]);
return ret;
}
}
图论
网络流(sap&dinic&zkw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//sap
ll sap(int u,ll flow){//注意编号从1开始(我太菜了QWQ)
if(u==T||!flow)return flow;
ll sum=0,tmp;
for(int i=Last[u],v;i;i=Next[i]){
v=End[i];
if(Len[i]&&dis[u]==dis[v]+1){
tmp=sap(v,min(Len[i],flow-sum));
Len[i]-=tmp,Len[i^1]+=tmp;
sum+=tmp;
if(sum==flow||dis[S]>=T+1)return sum;
}
}
if(dis[S]>=T+1)return sum;
cnt[dis[u]]--;
if(!cnt[dis[u]])dis[S]=T+1;
dis[u]++;
cnt[dis[u]]++;
return sum;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35//dinic
bool findpath(){
for(int i=0;i<=Cnt;++i)dis[i]=-1;
queue<int>Q;
dis[S]=0,Q.push(S);
while(Q.size()){
int u=Q.front();
Q.pop();
for(int i=Last[u],v;i;i=Next[i]){
v=End[i];
if(Flow[i]&&(!~dis[v])){
dis[v]=dis[u]+1,Q.push(v);
if(v==T)return 1;
}
}
}
return 0;
}
int dinic(int u,int flow){
if(u==T)return flow;
int sum=0,tmp;
for(int i=Last[u],v;i;i=Next[i]){
v=End[i];
if(Flow[i]&&dis[v]==dis[u]+1){
tmp=dinic(v,min(flow-sum,Flow[i]));
sum+=tmp,Flow[i]-=tmp,Flow[i^1]+=tmp;
if(sum==flow)return sum;
}
}
if(!sum)dis[u]=-1;
return sum;
}
void maxflow(){
while(findpath())Maxflow+=dinic(S,inf);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34//zkw费用流
int aug(int u,int flow){
if(u==T){
Mincost+=-dis[S]*flow,Maxflow+=flow;
return flow;
}
vis[u]=1;
int sum=0,tmp;
for(int i=Last[u],v;i;i=Next[i]){
v=End[i];
if(Flow[i]&&!vis[v]&&dis[u]-dis[v]+Cost[i]==0){
tmp=aug(v,min(flow-sum,Flow[i]));
sum+=tmp;
Flow[i]-=tmp,Flow[i^1]+=tmp;
if(sum==flow)return sum;
}
}
return sum;
}
bool mdf(){
int u,v,d=inf;
for(int i=2;i<=o;++i){
if(Flow[i]&&vis[u=St[i]]&&!vis[v=End[i]])d=min(d,dis[u]-dis[v]+Cost[i]);
}
if(d==inf)return 0;
for(int i=S;i<=T;++i)if(vis[i])dis[i]-=d;
return 1;
}
void zkw(){
do{
for(int i=S;i<=T;++i)vis[i]=0;
aug(S,inf);
}while(mdf());
}Tarjan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//Tarjan
void tarjan(int u){
vis[u]=1,st.push(u);
dfn[u]=low[u]=++vt;
for(int i=Last[u],v;i;i=Next[i]){
v=End[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
suc++;
int tmp=0;
while(tmp!=u){
tmp=st.top();
vis[tmp]=0,st.pop();
bel[tmp]=suc;
}
}
}Kruskal重构树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//Kruskal重构树
struct edge{//NOI2018 归程
int u,v,len,hight;
bool operator<(const edge &x)const{
return hight>x.hight;
}
}E[maxn];
int find(int x){
return (x==fa[x])?x:fa[x]=find(fa[x]);
}
void kl(){
sort(E+1,E+1+M);
for(int i=1;i<=N;++i)fa[i]=i;
cnt=N;
for(int i=1,tot=0;i<=M;++i){
int U=find(E[i].u),V=find(E[i].v);
if(U!=V){
val[++cnt]=E[i].hight;
fa[cnt]=cnt,fa[U]=fa[V]=cnt;
ins(cnt,U,0),ins(cnt,V,0);
if(++tot==N-1)break;
}
}
}
字符串
Manacher
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//Manacher
void init(){
H[0]=-1,H[1]=0,Len=2;
for(int i=1;i<=N;++i){
scanf("%d",H[Len]);
Len++,H[Len]=0,Len++;
}
H[Len]=-2;
}
int Manacher(){
int ret=-1;
int Pos;
for(int i=1;i<Len;++i){
if(i<Max)R[i]=min(R[2*Pos-i],Max-i+1);
else R[i]=1;
while(H[i-R[i]]==H[i+R[i]])R[i]++;
if(Max<i+R[i]-1)Max=i+R[i]-1,Pos=i;
ret=max(ret,R[i]-1);
}
return ret;
}KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//KMP
void KMP(){
scanf("%s",A+1);
scanf("%s",B+1);
int lenA=strlen(A+1);
int lenB=strlen(B+1);
int j=0;
for(int i=2;i<=lenB;++i){
while(j&&B[j+1]!=B[i])j=fail[j];
if(B[j+1]==B[i])j++;
fail[i]=j;
}
j=0;
for(int i=1;i<=lenA;++i){
while(j>0&&B[j+1]!=A[i])j=fail[j];
if(B[j+1]==A[i])j++;
if(j==lenB){
//xxx
j=fail[j];
}
}
}自动机(AC自动机&后缀自动机)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26//AC自动机
namespace ACAM{//滑稽
int ch[maxn<<1][26],fail[maxn<<1],tot;
void extend(){
scanf("%s",s+1);
int p=0,t,len=strlen(s+1);
for(int i=1;i<=len;++i){
t=s[i]-'a';
if(!ch[p][t])ch[p][t]=++tot;
p=ch[p][t];
}
//xxx
}
void getfail(){
queue<int>Q;
for(int t=0;t<26;++t)if(ch[0][t])Q.push(ch[0][t]);
while(Q.size()){
int x=Q.front();
Q.pop();
for(int t=0;t<26;++t){
if(ch[x][i])Q.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i];
else ch[x][i]=ch[fail[x]][i];
}
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//后缀自动机
namespace SAM{
map<ll,int>ch[maxn<<1];
int par[maxn<<1],mx[maxn<<1];
int tot,las;
void init(){
for(int i=1;i<=tot;++i)ch[i].clear(),mx[i]=par[i]=0;
las=tot=1;
}
void extend(ll c){
int p=las,np=++tot;
mx[np]=mx[p]+1;
for(;p&&(!ch[p].count(c));p=par[p])ch[p][c]=np;
las=np;
if(!p){par[np]=1;return;}
int q=ch[p][c];
if(mx[q]==mx[p]+1){par[np]=q;return;}
int nq=++tot;
ch[nq]=ch[q],mx[nq]=mx[p]+1,par[nq]=par[q];
par[q]=par[np]=nq;
for(;p&&ch[p].count(c)&&ch[p][c]==q;p=par[p])ch[p][c]=nq;
}
}