NTT
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct fastio{ 8 static const int N=12; 9 int b[N],B; 10 int ru(){ 11 int x=0; 12 char c=getchar(); 13 while(c<48)c=getchar(); 14 while(c>47)x=x*10+c-48,c=getchar(); 15 return x; 16 } 17 int ri(){ 18 int x=0,o=1; 19 char c=getchar(); 20 while(c<45)c=getchar(); 21 if(c=='-')o=-1,c=getchar(); 22 while(c>47)x=x*10+c-48,c=getchar(); 23 return x*o; 24 } 25 void wu(int x){ 26 if(!x){ 27 putchar('0'); 28 return; 29 } 30 B=0; 31 while(x)b[++B]=x%10,x/=10; 32 while(B)putchar(48+b[B--]); 33 } 34 void wi(int x){ 35 if(x<0)putchar('-'),x=-x; 36 if(!x){ 37 putchar('0'); 38 return; 39 } 40 B=0; 41 while(x)b[++B]=x%10,x/=10; 42 while(B)putchar(48+b[B--]); 43 } 44 }F; 45 struct FFT{ 46 static const int N=262222,M=998244353ll; 47 int n,m; 48 ll a[N],b[N],w[N],w2[N],r; 49 ll P(ll x,ll k){ 50 ll ans=1; 51 while(k){ 52 if(k&1)ans=ans*x%M; 53 x=x*x%M,k>>=1; 54 } 55 return ans; 56 } 57 void fft(ll *a,ll *w){ 58 for(int i=0,j=0;i<n;++i){ 59 if(i<j)swap(a[i],a[j]); 60 for(int k=n>>1;(j^=k)<k;k>>=1); 61 } 62 for(int i=2;i<=n;i<<=1){ 63 for(int j=0;j<n;j+=i){ 64 for(int k=0;k<(i>>1);++k){ 65 int l=j+k,r=l+(i>>1); 66 ll o=a[r]*w[n/i*k]%M; 67 a[r]=(a[l]+M-o)%M,a[l]=(a[l]+o)%M; 68 } 69 } 70 } 71 } 72 void mul(){ 73 fft(a,w),fft(b,w); 74 for(int i=0;i<n;++i)a[i]=a[i]*b[i]%M*r%M; 75 fft(a,w2); 76 } 77 void init(){ 78 n=F.ru(),m=F.ru(); 79 for(int i=0;i<n;++i)a[i]=F.ru(); 80 for(int i=0;i<m;++i)b[i]=F.ru(); 81 m+=n-2,n=1; 82 while(n<=m)n<<=1; 83 r=P(n,M-2),w[0]=w2[0]=1,w[1]=w2[n-1]=P(3,(M-1)/n); 84 for(int i=2;i<n;++i)w[i]=w2[n-i]=w[i-1]*w[1]%M; 85 } 86 void out(){ 87 for(int i=0;i<m;++i)F.wu((int)a[i]),putchar(' '); 88 F.wu((int)a[m]),putchar(' '); 89 } 90 }_; 91 int main(){ 92 _.init(),_.mul(),_.out(); 93 return 0; 94 }
dinic
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define orz 1000000007 using namespace std; int gi(){ char c=getchar(); int x=0; while(c<48)c=getchar(); while(c>47)x=x*10+c-48,c=getchar(); return x; } struct E{int x,y,z;}; vector<E> v[10005]; void add(int x,int y,int z){ E X,Y; X.x=y,X.y=z,X.z=v[y].size(); Y.x=x,Y.y=0,Y.z=v[x].size(); v[x].pb(X),v[y].pb(Y); } int n,m,s,t,ans; int l[10005],i[10005],q[10005],L,R; int dfs(int x,int y){ if(x==t) return y; int ret=0; for(;i[x]<v[x].size();++i[x]){ E &e=v[x][i[x]]; if(!e.y||l[e.x]!=l[x]+1) continue; int d=dfs(e.x,min(y,e.y)); if(!d) continue; e.y-=d,v[e.x][e.z].y+=d,ret+=d,y-=d; if(!y) return ret; } l[x]=-1; return ret; } int main(){ n=gi();m=gi();s=gi();t=gi(); for(int i=1;i<=m;++i){ int x,y,z; x=gi();y=gi();z=gi(); add(x,y,z); } while(1){ memset(i,0,sizeof(i)); memset(l,-1,sizeof(l)); l[s]=0,L=0,R=1,q[1]=s; while(L!=R){ int x=q[++L]; for(int i=0;i<v[x].size();++i){ if(v[x][i].y&&l[v[x][i].x]==-1)l[v[x][i].x]=l[x]+1,q[++R]=v[x][i].x; } } if(l[t]==-1) break; ans+=dfs(s,orz); } printf("%d ",ans); return 0; }
费用流(dijkstra)
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct E{int x,y,z,c;}; 8 struct F{ 9 vector<E> v[5005]; 10 int n,s,t,ans,res,h[5005],d[5005],pv[5005],pe[5005]; 11 void upd(int &x,int y){if(x>y)x=y;} 12 void init(){ 13 for(int i=1;i<=n;++i)v[i].clear(); 14 } 15 void add(int x,int y,int z,int c){ 16 E X,Y; 17 X.x=y,X.y=z,X.z=v[y].size(),X.c=c; 18 Y.x=x,Y.y=0,Y.z=v[x].size(),Y.c=-c; 19 v[x].pb(X),v[y].pb(Y); 20 } 21 void flow(){ 22 ans=res=0; 23 memset(h,0,sizeof(h)); 24 while(1){ 25 for(int i=1;i<=n;++i)d[i]=orz; 26 d[s]=0; 27 priority_queue<pair<int,int> >q; 28 q.push(mp(0,s)); 29 while(!q.empty()){ 30 int dd=-q.top().first,k=q.top().second; 31 q.pop(); 32 if(d[k]!=dd) continue; 33 for(int i=0;i<v[k].size();++i){ 34 E &e=v[k][i]; 35 if(e.y){ 36 int u=e.x,D=dd+e.c+h[k]-h[u]; 37 if(d[u]>D)d[u]=D,pv[u]=k,pe[u]=i,q.push(mp(-D,u)); 38 } 39 } 40 } 41 if(d[t]==orz) return; 42 for(int i=1;i<=n;++i)h[i]+=d[i]; 43 int o=orz; 44 for(int i=t;i!=s;i=pv[i])upd(o,v[pv[i]][pe[i]].y); 45 ans+=o,res+=o*h[t]; 46 for(int i=t;i!=s;i=pv[i]){ 47 E &e=v[pv[i]][pe[i]]; 48 e.y-=o,v[e.x][e.z].y+=o; 49 } 50 } 51 } 52 }f; 53 int m; 54 int r(){ 55 int x=0; 56 char c=getchar(); 57 while(c<48)c=getchar(); 58 while(c>47)x=x*10+c-48,c=getchar(); 59 return x; 60 } 61 int main(){ 62 f.n=r(),m=r(),f.s=r(),f.t=r(); 63 for(int i=1;i<=m;++i){ 64 int x,y,z,c; 65 x=r(),y=r(),z=r(),c=r(); 66 f.add(x,y,z,c); 67 } 68 f.flow(); 69 printf("%d %d ",f.ans,f.res); 70 return 0; 71 }
树链剖分
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int n,m,r,f[100005][18],d[100005],a[100005],s[100005],S=1,F[100005],P[100005]; 8 vector<int> v[100005]; 9 ll p; 10 struct bit{ 11 ll t[100005],t2[100005]; 12 void add(int l,int r,int x){ 13 int k=l; 14 ll o=(1-l)*1ll*x; 15 while(k<=n)t[k]=(t[k]+o)%p,k+=(k&-k); 16 k=l,o=x; 17 while(k<=n)t2[k]=(t2[k]+o)%p,k+=(k&-k); 18 k=r+1,o=r*1ll*x; 19 while(k<=n)t[k]=(t[k]+o)%p,k+=(k&-k); 20 k=r+1,o=-x; 21 while(k<=n)t2[k]=(t2[k]+o)%p,k+=(k&-k); 22 } 23 int get(int l,int r){ 24 ll ans1=0,ans2=0; 25 int k=r; 26 while(k)ans2+=t2[k],k-=(k&-k); 27 ans2*=r; 28 k=r; 29 while(k)ans2+=t[k],k-=(k&-k); 30 k=l-1; 31 while(k)ans1+=t2[k],k-=(k&-k); 32 ans1*=(l-1); 33 k=l-1; 34 while(k)ans1+=t[k],k-=(k&-k); 35 return (int)(((ans2-ans1)%p+p)%p); 36 } 37 }t; 38 39 void ope(int x,int y){ 40 d[x]=d[y]+1,f[x][0]=y,s[x]=1; 41 for(int i=0;i<17;++i)f[x][i+1]=f[f[x][i]][i]; 42 for(int i=0;i<v[x].size();++i)if(v[x][i]!=y)ope(v[x][i],x),s[x]+=s[v[x][i]]; 43 } 44 int lca(int x,int y){ 45 if(d[x]<d[y])swap(x,y); 46 for(int i=17;i>=0;--i)if(d[f[x][i]]>=d[y])x=f[x][i]; 47 if(x==y) return x; 48 for(int i=17;i>=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; 49 return f[x][0]; 50 } 51 void dfs(int x,int y){ 52 t.add(F[x],F[x],a[x]); 53 int son=0; 54 for(int i=0;i<v[x].size();++i)if(v[x][i]!=y&&s[v[x][i]]>s[son])son=v[x][i]; 55 if(!son) return; 56 F[son]=++S,P[son]=P[x],dfs(son,x); 57 for(int i=0;i<v[x].size();++i)if(v[x][i]!=y&&v[x][i]!=son)F[v[x][i]]=++S,P[v[x][i]]=v[x][i],dfs(v[x][i],x); 58 } 59 void change(int l,int r,int x){ 60 if(d[l]>d[r]) return; 61 if(d[P[r]]>=d[l])t.add(F[P[r]],F[r],x),change(l,f[P[r]][0],x); 62 else t.add(F[l],F[r],x); 63 } 64 int answer(int l,int r){ 65 if(d[l]>d[r]) return 0; 66 if(d[P[r]]>=d[l]) return (t.get(F[P[r]],F[r])+answer(l,f[P[r]][0]))%p; 67 return t.get(F[l],F[r]); 68 } 69 int main(){ 70 memset(t.t,0,sizeof(t.t)); 71 memset(t.t2,0,sizeof(t.t2)); 72 scanf("%d%d%d%lld",&n,&m,&r,&p); 73 for(int i=1;i<=n;++i)scanf("%d",a+i); 74 for(int i=1;i<n;++i){ 75 int x,y; 76 scanf("%d%d",&x,&y); 77 v[x].pb(y),v[y].pb(x); 78 } 79 ope(r,0),F[r]=1,P[r]=r,dfs(r,0); 80 for(int i=1;i<=m;++i){ 81 int T,x,y,z,k; 82 scanf("%d",&T); 83 if(T==1){ 84 scanf("%d%d%d",&x,&y,&k); 85 z=lca(x,y),change(z,x,k),change(z,y,k),change(z,z,-k); 86 } 87 else if(T==2){ 88 scanf("%d%d",&x,&y); 89 z=lca(x,y),printf("%d ",(int)((((answer(z,x)+answer(z,y))%p)-answer(z,z)+p)%p)); 90 } 91 else if(T==3){ 92 scanf("%d%d",&x,&k); 93 t.add(F[x],F[x]+s[x]-1,k); 94 } 95 else{ 96 scanf("%d",&x); 97 printf("%d ",t.get(F[x],F[x]+s[x]-1)); 98 } 99 } 100 return 0; 101 }
无旋treap
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct treap{ 8 int size,val,key; 9 treap* ch[2]; 10 }; 11 treap *empty,*root; 12 void init(treap *t,int x){t->val=x,t->key=rand(),t->size=1,t->ch[0]=t->ch[1]=empty;} 13 treap *merge(treap *x,treap *y){ 14 if(x==empty) return y; 15 if(y==empty) return x; 16 if(x->key<y->key){x->size+=y->size,x->ch[1]=merge(x->ch[1],y);return x;} 17 y->size+=x->size,y->ch[0]=merge(x,y->ch[0]);return y; 18 } 19 pair<treap*,treap*> split(treap *t,int k){ 20 if(t==empty) return mp(t,t); 21 pair<treap*,treap*> ret; 22 if(t->ch[0]->size>=k)ret=split(t->ch[0],k),t->ch[0]=ret.second,t->size-=k,ret.second=t; 23 else ret=split(t->ch[1],k-t->ch[0]->size-1),t->ch[1]=ret.first,t->size=k,ret.first=t; 24 return ret; 25 } 26 int rank(treap *t,int x){ 27 if(t==empty) return 0; 28 if(t->val>=x) return rank(t->ch[0],x); 29 return rank(t->ch[1],x)+t->ch[0]->size+1; 30 } 31 int get(treap *t,int k){ 32 if(t->ch[0]->size>=k) return get(t->ch[0],k); 33 if(t->ch[0]->size+1==k) return t->val; 34 return get(t->ch[1],k-t->ch[0]->size-1); 35 } 36 void ins(int x){ 37 treap *v=new treap; 38 init(v,x); 39 pair<treap*,treap*> p=split(root,rank(root,x)); 40 root=merge(merge(p.first,v),p.second); 41 } 42 void del(int k){ 43 pair<treap*,treap*> p=split(root,k-1),q=split(p.second,1); 44 root=merge(p.first,q.second); 45 } 46 int main(){ 47 empty=new treap,root=new treap; 48 empty->size=0,empty->val=0,empty->key=0,empty->ch[0]=empty->ch[1]=empty; 49 init(root,orz); 50 int T; 51 scanf("%d",&T); 52 while(T--){ 53 int t,x; 54 scanf("%d%d",&t,&x); 55 if(t==1)ins(x); 56 if(t==2)del(rank(root,x)+1); 57 if(t==3)printf("%d ",rank(root,x)+1); 58 if(t==4)printf("%d ",get(root,x)); 59 if(t==5)printf("%d ",get(root,rank(root,x))); 60 if(t==6)printf("%d ",get(root,rank(root,x+1)+1)); 61 } 62 return 0; 63 }
二逼平衡树(CDQ分治+整体二分)
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 /* 8 CDQ: 9 get rank- t=0 10 get rank t=1 11 insert t=2 12 remove t=3 13 l=pos k=num 14 go: 15 find kth t=1 l=left r=right k=kth 16 insert t=2 17 remove t=3 18 */ 19 struct S{int t,l,r,k,i;}p[500005],q[500005],q2[500005]; 20 struct BIT{int t[100005];}T; 21 int n,m,a[50005],b[50005],t[50005],l[50005],r[50005],k[50005],ans[50005],P; 22 pair<int,int> Q[100005]; 23 int back[100005],O; 24 void I(int t,int l,int r,int k,int i){p[++P].t=t,p[P].l=l,p[P].r=r,p[P].k=k,p[P].i=i;} 25 void add(int x,int k){while(x<=n)T.t[x]+=k,x+=(x&-x);} 26 int sum(int x){ 27 int ans=0; 28 while(x)ans+=T.t[x],x-=(x&-x); 29 return ans; 30 } 31 void cdq(int l,int r){ 32 if(l>=r) return; 33 int m=(l+r)>>1,L=l,R=m+1; 34 cdq(l,m),cdq(m+1,r); 35 for(int i=l;i<=r;++i){ 36 if(L<=m&&(R>r||p[L].k<p[R].k)){ 37 q[i]=p[L++]; 38 if(q[i].t==2)add(q[i].l,1); 39 else if(q[i].t==3)add(q[i].l,-1); 40 } 41 else{ 42 q[i]=p[R++]; 43 if(q[i].t==0)ans[q[i].i]-=sum(q[i].l); 44 else if(q[i].t==1)ans[q[i].i]+=sum(q[i].l); 45 } 46 } 47 for(int i=l;i<=m;++i){ 48 if(p[i].t==2)add(p[i].l,-1); 49 else if(p[i].t==3)add(p[i].l,1); 50 } 51 for(int i=l;i<=r;++i)p[i]=q[i]; 52 } 53 void go(int l,int r,int L,int R){ 54 if(l>r||L>R) return; 55 if(l==r){ 56 for(int i=L;i<=R;++i)if(p[i].t==1)ans[p[i].i]=back[l]; 57 return; 58 } 59 int m=(l+r)>>1,v=0,v2=0; 60 for(int i=L;i<=R;++i){ 61 if(p[i].t==2){ 62 if(p[i].k>m)q2[++v2]=p[i]; 63 else q[++v]=p[i],add(p[i].l,1); 64 } 65 else if(p[i].t==3){ 66 if(p[i].k>m)q2[++v2]=p[i]; 67 else q[++v]=p[i],add(p[i].l,-1); 68 } 69 else{ 70 int o=sum(p[i].r)-sum(p[i].l-1); 71 if(o>=p[i].k)q[++v]=p[i]; 72 else p[i].k-=o,q2[++v2]=p[i]; 73 } 74 } 75 for(int i=L;i<=R;++i){ 76 if(p[i].t==2){ 77 if(p[i].k<=m)add(p[i].l,-1); 78 } 79 else if(p[i].t==3){ 80 if(p[i].k<=m)add(p[i].l,1); 81 } 82 } 83 for(int i=1;i<=v;++i)p[L+i-1]=q[i]; 84 for(int i=1;i<=v2;++i)p[R-v2+i]=q2[i]; 85 go(l,m,L,L+v-1),go(m+1,r,L+v,R); 86 } 87 int main(){ 88 scanf("%d%d",&n,&m); 89 for(int i=1;i<=n;++i)scanf("%d",a+i),Q[i]=mp(a[i],i); 90 for(int i=1;i<=m;++i){ 91 scanf("%d",t+i); 92 if(t[i]==3)scanf("%d%d",l+i,k+i); 93 else scanf("%d%d%d",l+i,r+i,k+i); 94 if(t[i]!=2)Q[n+i]=mp(k[i],i+n),ans[i]=1; 95 } 96 sort(Q+1,Q+n+m+1); 97 for(int i=1;i<=n+m;++i){ 98 if(i==1||Q[i].first!=Q[i-1].first)back[++O]=Q[i].first; 99 if(Q[i].second>n)k[Q[i].second-n]=O; 100 else a[Q[i].second]=b[Q[i].second]=O; 101 } 102 for(int i=1;i<=n;++i)I(2,i,0,a[i],i); 103 for(int i=1;i<=m;++i){ 104 if(t[i]==3)I(3,l[i],0,b[l[i]],i),I(2,l[i],0,b[l[i]]=k[i],i); 105 else if(t[i]!=2){ 106 if(t[i]==5)++k[i]; 107 else if(t[i]==4)ans[i]=0; 108 I(1,r[i],0,k[i],i); 109 if(l[i]>1)I(0,l[i]-1,0,k[i],i); 110 } 111 else ans[i]=k[i]; 112 } 113 cdq(1,P); 114 P=0; 115 for(int i=1;i<=n;++i)I(2,i,0,a[i],i),b[i]=a[i]; 116 for(int i=1;i<=m;++i){ 117 if(t[i]==3)I(3,l[i],0,b[l[i]],i),I(2,l[i],0,b[l[i]]=k[i],i); 118 else if(t[i]!=1)I(1,l[i],r[i],ans[i],i); 119 } 120 go(1,O+1,1,P); 121 for(int i=1;i<=m;++i)if(t[i]!=3)printf("%d ",ans[i]); 122 return 0; 123 }
主席树
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct T{ 8 int l,r,s; 9 }t[4000005]; 10 int n,m,cnt,r[100005]; 11 void add(int l,int r,int x,int y,int k){ 12 t[x]=t[y],++t[x].s; 13 if(l==r) return; 14 int m=(l+r)>>1; 15 if(k<=m)add(l,m,t[x].l=++cnt,t[y].l,k); 16 else add(m+1,r,t[x].r=++cnt,t[y].r,k); 17 } 18 int get(int l,int r,int x,int y,int k){ 19 if(l==r) return l; 20 int m=(l+r)>>1; 21 if(t[t[x].l].s-t[t[y].l].s>=k) return get(l,m,t[x].l,t[y].l,k); 22 return get(m+1,r,t[x].r,t[y].r,k-t[t[x].l].s+t[t[y].l].s); 23 } 24 int main(){ 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=n;++i){ 27 int x; 28 scanf("%d",&x); 29 add(-orz,orz,r[i]=++cnt,r[i-1],x); 30 } 31 for(int i=1;i<=m;++i){ 32 int x,y,k; 33 scanf("%d%d%d",&x,&y,&k); 34 printf("%d ",get(-orz,orz,r[y],r[x-1],k)); 35 } 36 return 0; 37 }
KMP
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int a[1000005],b[1000005],n,m,f[1000005]; 8 string s1,s2; 9 int main(){ 10 ios::sync_with_stdio(0); 11 cin>>s1>>s2; 12 n=s1.size(),m=s2.size(); 13 for(int i=1;i<=n;++i)a[i]=s1[i-1]; 14 for(int i=1;i<=m;++i)b[i]=s2[i-1]; 15 int k=0; 16 for(int i=2;i<=m;++i){ 17 while(b[k+1]!=b[i]&&k)k=f[k]; 18 if(b[k+1]==b[i])++k; 19 f[i]=k; 20 } 21 k=0; 22 for(int i=1;i<=n;++i){ 23 while(b[k+1]!=a[i]&&k)k=f[k]; 24 if(b[k+1]==a[i])++k; 25 if(k==m)printf("%d ",i-m+1); 26 } 27 for(int i=1;i<m;++i)printf("%d ",f[i]); 28 printf("%d ",f[m]); 29 return 0; 30 }
manacher
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int a[22000005],f[22000005],n,k,ans; 8 int main() 9 { 10 a[0]='+'; 11 a[++n]='?'; 12 char c=getchar(); 13 while(c>='a'){ 14 a[++n]=c; 15 a[++n]='?'; 16 c=getchar(); 17 } 18 a[n+1]='-'; 19 for(int i=1;i<=n;i++){ 20 if(i<k+f[k])f[i]=min(f[k]+k-i,f[k+k-i]); 21 while(a[i-f[i]]==a[i+f[i]])f[i]++; 22 if(f[i]+i>f[k]+k)k=i; 23 } 24 for(int i=1;i<=n;i++)ans=max(ans,f[i]); 25 printf("%d ",ans-1); 26 return 0; 27 }
后缀数组
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int n,a[100005],cnt[200],r[240005],R[100005],p[100005],q[100005],C[100005],sa[100005],h[100005]; 8 int main(){ 9 char c=getchar(); 10 while(c!=' ')a[++n]=c,cnt[c]=1,c=getchar(); 11 for(int i=40;i<=150;++i)cnt[i]+=cnt[i-1]; 12 for(int i=1;i<=n;++i)r[i]=cnt[a[i]]; 13 for(int i=2;i<=n;++i)++C[r[i]]; 14 C[0]=1; 15 for(int i=1;i<=n;++i)C[i]+=C[i-1]; 16 for(int i=n;i;--i)q[C[r[i+1]]--]=i; 17 memset(C,0,sizeof(C)); 18 for(int _=1;_<n;_<<=1){ 19 int __=_<<1; 20 for(int i=1;i<=n;++i)++C[r[i]]; 21 for(int i=1;i<=n;++i)C[i]+=C[i-1]; 22 for(int i=n;i;--i)p[C[r[q[i]]]--]=q[i]; 23 memset(C,0,sizeof(C)); 24 int k=0,K=__; 25 if(__<n){ 26 for(int i=1;i<=__;++i)q[i]=n+1-i; 27 } 28 for(int i=1;i<=n;++i){ 29 if(r[p[i]]!=r[p[i-1]]||r[p[i]+_]!=r[p[i-1]+_])++k; 30 R[p[i]]=k; 31 if(p[i]>__)q[++K]=p[i]-__; 32 } 33 for(int i=1;i<=n;++i)r[i]=R[i]; 34 } 35 for(int i=1;i<=n;++i)sa[r[i]]=i; 36 for(int i=1;i<n;++i)printf("%d ",sa[i]); 37 printf("%d ",sa[n]); 38 int k=0; 39 for(int i=1;i<=n;++i){ 40 if(r[i]==1){ 41 k=0; 42 continue; 43 } 44 if(k)--k; 45 int j=sa[r[i]-1]; 46 while(a[i+k]==a[j+k])++k; 47 h[r[i]]=k; 48 } 49 for(int i=2;i<n;++i)printf("%d ",h[i]); 50 if(n>1)printf("%d ",h[n]); 51 return 0; 52 }
凸包
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 #define X first 7 #define Y second 8 using namespace std; 9 struct P{int x,y;}; 10 P mns(P x,P y){x.x-=y.x,x.y-=y.y;return x;} 11 int det(P x,P y){return x.x*y.y-x.y*y.x;} 12 int norm(P x){return x.x*x.x+x.y*x.y;} 13 int n; 14 pair<int,int> p[50005]; 15 P a[50005],b[50005],c[50005]; 16 int lb,lc; 17 int ans; 18 int main(){ 19 scanf("%d",&n); 20 for(int i=1;i<=n;++i)scanf("%d%d",&p[i].X,&p[i].Y); 21 sort(p+1,p+n+1); 22 for(int i=1;i<=n;++i)a[i].x=p[i].X,a[i].y=p[i].Y; 23 for(int i=1;i<=n;++i){ 24 while(lb>1&&det(mns(b[lb],b[lb-1]),mns(a[i],b[lb]))>=0)--lb; 25 b[++lb]=a[i]; 26 } 27 for(int i=1;i<=n;++i){ 28 while(lc>1&&det(mns(c[lc],c[lc-1]),mns(a[i],c[lc]))<=0)--lc; 29 c[++lc]=a[i]; 30 } 31 for(int i=1;i<=lb;++i){ 32 for(int j=1;j<=lc;++j)ans=max(ans,norm(mns(b[i],c[j]))); 33 } 34 printf("%d ",ans); 35 return 0; 36 }
一般图最大匹配(带花树)
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define orz 1000000007 using namespace std; int n,m,mat[505],pre[505],ans,cnt,a[505],fa[505],c[505],q[505],ql,qr; vector<int> v[505]; int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);} int lca(int x,int y){ ++cnt; x=get(x),y=get(y); while(1){ if(x){ if(a[x]==cnt) return x; a[x]=cnt,x=get(pre[mat[x]]); } swap(x,y); } } void bl(int x,int y,int z){ while(get(x)!=z){ pre[x]=y; if(c[mat[x]]==1)q[++qr]=mat[x],c[mat[x]]=0; if(fa[x]==x)fa[x]=z; if(fa[mat[x]]==mat[x])fa[mat[x]]=z; y=mat[x],x=pre[y]; } } bool go(int x){ for(int i=1;i<=n;++i)fa[i]=i; memset(c,-1,sizeof(c)); c[x]=0,qr=1,ql=0,q[1]=x; while(ql<qr){ int o=q[++ql]; for(int j=0;j<v[o].size();++j){ int p=v[o][j]; if(c[p]==-1){ pre[p]=o,c[p]=1; if(!mat[p]){ while(o){ int t=mat[o]; mat[o]=p,mat[p]=o; p=t,o=pre[t]; } return 1; } q[++qr]=mat[p],c[mat[p]]=0; } else if(!c[p]){ int t=lca(o,p); bl(o,p,t),bl(p,o,t); } } } return 0; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ int x,y; scanf("%d%d",&x,&y); v[x].pb(y),v[y].pb(x); } for(int i=1;i<=n;++i)if(!mat[i]&&go(i))++ans; printf("%d ",ans); for(int i=1;i<n;++i)printf("%d ",mat[i]); printf("%d ",mat[n]); return 0; }
一般图最大匹配(乱搞)
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define orz 1000000007 using namespace std; int n,m,a[505],u[505],ans[505],res,p[505]; vector<int> v[505]; bool dfs(int x){ u[x]=1; random_shuffle(v[x].begin(),v[x].end()); for(int i=0;i<v[x].size();++i){ int y=v[x][i]; if(!a[y]){ a[x]=y,a[y]=x; return 1; } } for(int i=0;i<v[x].size();++i){ int y=v[x][i],z=a[y]; if(u[z]) continue; a[x]=y,a[y]=x,a[z]=0; if(dfs(z)) return 1; a[x]=0,a[y]=z,a[z]=y; } return 0; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ int x,y; scanf("%d%d",&x,&y); v[x].pb(y),v[y].pb(x); } for(int i=1;i<=n;++i)p[i]=i; for(int _=10;_;--_){ random_shuffle(p+1,p+n+1); for(int i=1;i<=n;++i){ if(a[p[i]]) continue; memset(u,0,sizeof(u)); dfs(p[i]); } int cnt=0; for(int i=1;i<=n;++i)if(a[i])++cnt; if(cnt/2>res){ res=cnt/2; for(int i=1;i<=n;++i)ans[i]=a[i]; } } printf("%d ",res); for(int i=1;i<n;++i)printf("%d ",ans[i]); printf("%d ",ans[n]); return 0; }
二分图最大权匹配
#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define orz 1000000007 using namespace std; int nl,nr,n,m,f[405][405],lx[405],ly[405],vx[405],vy[405],sl[405]; int q[405],ql,qr,pre[405],ml[405],mr[405],out[405]; void go(int x){ while(1){ ql=0,qr=1,vx[x]=1,q[1]=x; while(ql<qr){ int o=q[++ql]; for(int i=1;i<=n;++i){ if(vy[i]) continue; int t=lx[o]+ly[i]-f[o][i]; if(t>sl[i]) continue; pre[i]=o; if(!t){ if(!ml[i]){ while(i){ ml[i]=pre[i]; swap(i,mr[pre[i]]); } return; } q[++qr]=ml[i]; vy[i]=vx[ml[i]]=1; } else sl[i]=t; } } int o,O=orz; for(int i=1;i<=n;++i)if(!vy[i]&&O>sl[i])o=i,O=sl[i]; for(int i=1;i<=n;++i){ if(vx[i])lx[i]-=O; if(vy[i])ly[i]+=O; else sl[i]-=O; } if(!ml[o]){ while(o){ ml[o]=pre[o]; swap(o,mr[pre[o]]); } return; } vy[o]=1,x=ml[o]; } } int main(){ scanf("%d%d%d",&nl,&nr,&m); n=max(nl,nr); for(int i=1;i<=m;++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); f[x][y]=z; lx[x]=max(lx[x],z); } for(int i=1;i<=n;++i){ memset(vx,0,sizeof(vx)); memset(vy,0,sizeof(vy)); for(int j=1;j<=n;++j)sl[j]=orz; go(i); } ll ans=0; for(int i=1;i<=n;++i)ans+=lx[i]+ly[i]; printf("%lld ",ans); for(int i=1;i<=nl;++i)out[i]=f[i][mr[i]]?mr[i]:0; for(int i=1;i<nl;++i)printf("%d ",out[i]); printf("%d ",out[nl]); return 0; }
多项式求逆
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define M 998244353ll 6 using namespace std; 7 struct T{ 8 int n; 9 ll a[524444],b[524444],c[524444],w[524444],w2[524444],r; 10 ll P(ll x,ll k){ 11 ll ans=1; 12 while(k){ 13 if(k&1ll)ans=ans*x%M; 14 k>>=1,x=x*x%M; 15 } 16 return ans; 17 } 18 void ntt(ll *a,ll *w){ 19 for(int i=0,j=0;i<n;++i){ 20 if(i<j)swap(a[i],a[j]); 21 for(int k=n>>1;(j^=k)<k;k>>=1); 22 } 23 for(int i=2;i<=n;i<<=1){ 24 for(int j=0;j<n;j+=i){ 25 for(int k=0;k<(i>>1);++k){ 26 int l=j+k,r=l+(i>>1); 27 ll o=a[r]*w[n/i*k]%M; 28 a[r]=(a[l]+M-o)%M,a[l]=(a[l]+o)%M; 29 } 30 } 31 } 32 } 33 void init(){ 34 r=P(n,M-2),w[0]=w2[0]=1,w[1]=w2[n-1]=P(3,(M-1)/n); 35 for(int i=2;i<n;++i)w[i]=w2[n-i]=w[i-1]*w[1]%M; 36 } 37 void mul(){ 38 init(); 39 ntt(a,w),ntt(b,w); 40 for(int i=0;i<n;++i)c[i]=a[i]*b[i]%M*r%M; 41 ntt(c,w2); 42 } 43 }t; 44 int n; 45 ll a[266666],b[266666]; 46 int main(){ 47 scanf("%d",&n); 48 for(int i=0;i<n;++i)scanf("%d",a+i); 49 b[0]=t.P(a[0],M-2ll); 50 for(int d=2;d<=262144;d<<=1){ 51 t.n=d; 52 for(int i=0;i<(d>>1);++i)t.a[i]=a[i],t.b[i]=b[i]; 53 for(int i=d>>1;i<d;++i)t.a[i]=t.b[i]=0; 54 t.mul(); 55 t.n=d<<1; 56 for(int i=0;i<d;++i)t.a[i]=t.c[i],t.b[i]=b[i]; 57 for(int i=d;i<(d<<1);++i)t.a[i]=t.b[i]=0; 58 t.mul(); 59 for(int i=0;i<d;++i)b[i]=(b[i]*2ll-t.c[i]+M)%M; 60 } 61 for(int i=0;i<n-1;++i)printf("%lld ",b[i]); 62 printf("%lld ",b[n-1]); 63 return 0; 64 }
杜教筛
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int T,n,f[5000005],p[800005],P; 8 ll pha[5000005],phb[444],mua[5000005],mub[444]; 9 bool PHB[444],MUB[444]; 10 ll getph(int x){ 11 if(x<=5000000) return pha[x]; 12 int y=n/x; 13 if(PHB[y]&&n/y==x) return phb[y]; 14 ll ret=x*(x+1ll)/2ll; 15 for(int l=2,r;l<=x;l=r+1){ 16 r=x/(x/l); 17 ret-=(r-l+1ll)*getph(x/l); 18 } 19 if(n/y==x)PHB[y]=1,phb[y]=ret; 20 return ret; 21 } 22 ll getmu(int x){ 23 if(x<=5000000) return mua[x]; 24 int y=n/x; 25 if(MUB[y]&&n/y==x) return mub[y]; 26 ll ret=1; 27 for(int l=2,r;l<=x;l=r+1){ 28 r=x/(x/l); 29 ret-=(r-l+1ll)*getmu(x/l); 30 } 31 if(n/y==x)MUB[y]=1,mub[y]=ret; 32 return ret; 33 } 34 int main(){ 35 pha[1]=mua[1]=1; 36 for(int i=2;i<=5000000;++i){ 37 if(!f[i])p[++P]=i; 38 for(int j=1;j<=P&&p[j]<=5000000/i;++j){ 39 f[p[j]*i]=p[j]; 40 if(i%p[j]==0) break; 41 } 42 } 43 for(int i=2;i<=5000000;++i){ 44 if(!f[i])pha[i]=i-1,mua[i]=-1; 45 else{ 46 int o=i/f[i]; 47 if(o%f[i]==0)pha[i]=pha[o]*f[i],mua[i]=0; 48 else pha[i]=pha[o]*(f[i]-1),mua[i]=-mua[o]; 49 } 50 } 51 for(int i=2;i<=5000000;++i)pha[i]+=pha[i-1],mua[i]+=mua[i-1]; 52 scanf("%d",&T); 53 while(T--){ 54 memset(phb,0,sizeof(phb)); 55 memset(mub,0,sizeof(mub)); 56 memset(PHB,0,sizeof(PHB)); 57 memset(MUB,0,sizeof(MUB)); 58 scanf("%d",&n); 59 printf("%lld %lld ",getph(n),getmu(n)); 60 } 61 return 0; 62 }
任意模数NTT
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define C pair<long double,long double> 6 #define X first 7 #define Y second 8 using namespace std; 9 struct MTT{ 10 int n,m,A[262222],B[262222],ans[262222]; 11 ll P; 12 C w[262222],w2[262222],a[262222],b[262222],a2[262222],b2[262222]; 13 C mul(C &x,C &y){ 14 return mp(x.X*y.X-x.Y*y.Y,x.X*y.Y+x.Y*y.X); 15 } 16 void gen(){ 17 long double pi=acos(-1.0); 18 w2[0]=w[0]=mp(1.0,0.0); 19 for(int i=1;i<n;++i)w2[n-i]=w[i]=mp(cos(2.0*i*pi/n),sin(2.0*i*pi/n)); 20 } 21 void fft(C *a,C *w){ 22 for(int i=0,j=0;i<n;++i){ 23 if(i<j)swap(a[i],a[j]); 24 for(int k=n>>1;(j^=k)<k;k>>=1); 25 } 26 for(int i=2;i<=n;i<<=1){ 27 for(int j=0;j<n;j+=i){ 28 for(int k=0;k<(i>>1);++k){ 29 int l=j+k,r=l+(i>>1); 30 C o=mul(a[r],w[n/i*k]); 31 a[r].X=a[l].X-o.X,a[r].Y=a[l].Y-o.Y,a[l].X+=o.X,a[l].Y+=o.Y; 32 } 33 } 34 } 35 } 36 void mtt(){ 37 gen(); 38 for(int i=0;i<n;++i)a[i]=mp(A[i]&32767,A[i]>>15),b[i]=mp(B[i]&32767,B[i]>>15); 39 fft(a,w),fft(b,w); 40 for(int i=0;i<n;++i){ 41 int j=(i?n-i:0); 42 C aa,bb,cc,dd,ac,ad,bc,bd; 43 aa=mp((a[i].X+a[j].X)*0.5,(a[i].Y-a[j].Y)*0.5); 44 bb=mp((a[i].Y+a[j].Y)*0.5,(a[j].X-a[i].X)*0.5); 45 cc=mp((b[i].X+b[j].X)*0.5,(b[i].Y-b[j].Y)*0.5); 46 dd=mp((b[i].Y+b[j].Y)*0.5,(b[j].X-b[i].X)*0.5); 47 ac=mul(aa,cc),ad=mul(aa,dd),bc=mul(bb,cc),bd=mul(bb,dd); 48 a2[j]=mp(ac.X-ad.Y,ac.Y+ad.X),b2[j]=mp(bc.X-bd.Y,bc.Y+bd.X); 49 } 50 fft(a2,w),fft(b2,w); 51 for(int i=0;i<n;++i){ 52 ll aa,bb,cc,dd; 53 aa=a2[i].X/n+0.5,bb=a2[i].Y/n+0.5,cc=b2[i].X/n+0.5,dd=b2[i].Y/n+0.5; 54 aa%=P,bb%=P,cc%=P,dd%=P; 55 ll o=aa+(bb+cc)*32768ll%P+dd*32768ll%P*32768ll%P; 56 o=(o%P+P)%P; 57 ans[i]=o; 58 } 59 } 60 void solve(){ 61 for(int i=0;i<=n;++i)A[i]=(A[i]%P+P)%P; 62 for(int i=0;i<=m;++i)B[i]=(B[i]%P+P)%P; 63 m+=n,n=1; 64 while(n<=m)n<<=1; 65 mtt(); 66 } 67 }_; 68 int main(){ 69 scanf("%d%d%lld",&_.n,&_.m,&_.P); 70 for(int i=0;i<=_.n;++i)scanf("%d",_.A+i); 71 for(int i=0;i<=_.m;++i)scanf("%d",_.B+i); 72 _.solve(); 73 for(int i=0;i<_.m;++i)printf("%d ",_.ans[i]); 74 printf("%d ",_.ans[_.m]); 75 return 0; 76 }
最小树形图
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int n,m,r,x[10005],y[10005],z[10005],d[105],u[105],id[105],pre[105]; 8 int solve(){ 9 int N=n,ans=0; 10 while(N){ 11 for(int i=1;i<=n;++i)d[i]=orz,u[i]=0,id[i]=0,pre[i]=0; 12 for(int i=1;i<=m;++i){ 13 if(x[i]!=y[i]&&d[y[i]]>z[i])d[y[i]]=z[i],pre[y[i]]=x[i]; 14 } 15 pre[r]=r,d[r]=0; 16 for(int i=1;i<=n;++i){ 17 if(!pre[i]) return -1; 18 ans+=d[i]; 19 } 20 N=0; 21 for(int i=1;i<=n;++i){ 22 if(u[i]) continue; 23 int I=i; 24 while(!u[I])u[I]=i,I=pre[I]; 25 if(u[I]!=i||I==r) continue; 26 ++N; 27 while(!id[I])id[I]=N,I=pre[I]; 28 } 29 if(!N) return ans; 30 for(int i=1;i<=n;++i)if(!id[i])id[i]=++N; 31 for(int i=1;i<=m;++i)z[i]-=d[y[i]],x[i]=id[x[i]],y[i]=id[y[i]]; 32 n=N,r=id[r]; 33 } 34 } 35 int main(){ 36 scanf("%d%d%d",&n,&m,&r); 37 for(int i=1;i<=m;++i)scanf("%d%d%d",x+i,y+i,z+i); 38 printf("%d ",solve()); 39 return 0; 40 }
BM-CH
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct BM{ 8 int n,cnt,f[2005]; 9 ll a[2005],d[2005]; 10 vector<ll> v[2005]; 11 ll fp(ll x,ll k=1000000005){ 12 ll ans=1; 13 while(k){ 14 if(k&1)ans=ans*x%orz; 15 k>>=1,x=x*x%orz; 16 } 17 return ans; 18 } 19 void solve(){ 20 while(cnt)v[cnt--].clear(); 21 v[0].clear(); 22 for(int i=1;i<=n;++i){ 23 ll t=a[i]; 24 for(int j=0;j<v[cnt].size();++j)(t-=v[cnt][j]*a[i-j-1])%=orz; 25 t=(t%orz+orz)%orz; 26 d[i]=t; 27 if(!t) continue; 28 f[cnt]=i; 29 if(!cnt){ 30 v[++cnt].resize(i); 31 continue; 32 } 33 ll mul=d[i]*fp(d[f[cnt-1]])%orz; 34 ++cnt; 35 v[cnt].resize(i-f[cnt-2]-1); 36 v[cnt].pb(mul); 37 for(int j=0;j<v[cnt-2].size();++j){ 38 ll o=-mul*v[cnt-2][j]; 39 o=(o%orz+orz)%orz; 40 v[cnt].pb(o); 41 } 42 if(v[cnt].size()<v[cnt-1].size())v[cnt].resize(v[cnt-1].size()); 43 for(int j=0;j<v[cnt-1].size();++j){ 44 v[cnt][j]+=v[cnt-1][j]; 45 if(v[cnt][j]>=orz)v[cnt][j]-=orz; 46 } 47 } 48 } 49 }b; 50 struct CH{ 51 int n,k; 52 ll f[2005],a[2005],g[2005],ans[2005],x[2005],res[4005]; 53 void add(ll &x,ll y){ 54 x+=y; 55 if(x>=orz)x-=orz; 56 } 57 void mul(ll *A,ll *B,ll *C){ 58 for(int i=0;i<=k*2-2;++i)res[i]=0; 59 for(int i=0;i<k;++i){ 60 for(int j=0;j<k;++j)(res[i+j]+=A[i]*B[j])%=orz; 61 } 62 for(int i=k*2-2;i>=k;--i){ 63 ll o=res[i]; 64 if(!o) continue; 65 for(int j=0;j<k;++j)add(res[i-k+j],orz-o*g[j]%orz); 66 } 67 for(int i=0;i<k;++i)C[i]=res[i]; 68 } 69 ll solve(){ 70 if(k==1){ 71 return f[0]*b.fp(a[0],n-k)%orz; 72 } 73 g[k]=1; 74 for(int i=1;i<=k;++i)g[k-i]=(orz-a[i-1])%orz; 75 for(int i=0;i<k;++i)ans[i]=x[i]=0; 76 ans[0]=1,x[1]=1; 77 int T=n; 78 while(T){ 79 if(T&1)mul(ans,x,ans); 80 T>>=1,mul(x,x,x); 81 } 82 ll ret=0; 83 for(int i=0;i<k;++i)(ret+=ans[i]*f[i])%=orz; 84 return (ret%orz+orz)%orz; 85 } 86 }c; 87 int main(){ 88 scanf("%d%d",&b.n,&c.n); 89 --c.n; 90 for(int i=1;i<=b.n;++i)scanf("%lld",b.a+i); 91 b.solve(); 92 c.k=b.v[b.cnt].size(); 93 for(int i=0;i<c.k;++i)c.f[i]=b.a[i+1],c.a[i]=b.v[b.cnt][i]; 94 printf("%lld ",c.solve()); 95 return 0; 96 }
无源汇上下界可行流
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct E{int x,y,z;}; 8 struct F{ 9 int n,s,t,l[205],i[205],q[205],ql,qr; 10 vector<E> v[205]; 11 void add(int x,int y,int z){ 12 E X,Y; 13 X.x=y,X.y=z,X.z=v[y].size(); 14 Y.x=x,Y.y=0,Y.z=v[x].size(); 15 v[x].pb(X),v[y].pb(Y); 16 } 17 void bfs(){ 18 memset(l,-1,sizeof(l)); 19 l[q[qr=1]=s]=0; 20 for(ql=1;ql<=qr;++ql){ 21 int x=q[ql]; 22 for(int i=0;i<v[x].size();++i)if(l[v[x][i].x]==-1&&v[x][i].y)l[q[++qr]=v[x][i].x]=l[x]+1; 23 } 24 } 25 int dfs(int x,int y){ 26 if(x==t) return y; 27 int ret=0; 28 for(;i[x]<v[x].size();++i[x]){ 29 E &e=v[x][i[x]]; 30 if(!e.y||l[e.x]!=l[x]+1) continue; 31 int d=dfs(e.x,min(e.y,y-ret)); 32 if(!d) continue; 33 ret+=d,e.y-=d,v[e.x][e.z].y+=d; 34 if(ret==y) return ret; 35 } 36 l[x]=-1; 37 return ret; 38 } 39 int dinic(){ 40 int ans=0; 41 while(1){ 42 bfs(); 43 if(l[t]==-1) return ans; 44 memset(i,0,sizeof(i)); 45 ans+=dfs(s,orz); 46 } 47 } 48 }_; 49 int n,m,s[11000],t[11000],l[11000],r[11000],S[205],T[205],res,rec[11000]; 50 int main(){ 51 scanf("%d%d",&n,&m); 52 _.n=_.t=n+2,_.s=n+1; 53 for(int i=1;i<=m;++i){ 54 scanf("%d%d%d%d",s+i,t+i,l+i,r+i); 55 if(l[i]>r[i]){ 56 puts("NO"); 57 return 0; 58 } 59 rec[i]=_.v[t[i]].size(); 60 _.add(s[i],t[i],r[i]-l[i]); 61 S[t[i]]+=l[i],T[s[i]]+=l[i],res+=l[i]; 62 } 63 for(int i=1;i<=n;++i)_.add(_.s,i,S[i]),_.add(i,_.t,T[i]); 64 res-=_.dinic(); 65 if(res)puts("NO"); 66 else{ 67 puts("YES"); 68 for(int i=1;i<=m;++i)printf("%d ",l[i]+_.v[t[i]][rec[i]].y); 69 } 70 return 0; 71 }
有源汇上下界最大流
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct E{int x,y,z;}; 8 struct F{ 9 int n,s,t,l[205],i[205],q[205],ql,qr; 10 vector<E> v[205]; 11 void add(int x,int y,int z){ 12 E X,Y; 13 X.x=y,X.y=z,X.z=v[y].size(); 14 Y.x=x,Y.y=0,Y.z=v[x].size(); 15 v[x].pb(X),v[y].pb(Y); 16 } 17 void bfs(){ 18 memset(l,-1,sizeof(l)); 19 l[q[qr=1]=s]=0; 20 for(ql=1;ql<=qr;++ql){ 21 int x=q[ql]; 22 for(int i=0;i<v[x].size();++i)if(l[v[x][i].x]==-1&&v[x][i].y)l[q[++qr]=v[x][i].x]=l[x]+1; 23 } 24 } 25 int dfs(int x,int y){ 26 if(x==t) return y; 27 int ret=0; 28 for(;i[x]<v[x].size();++i[x]){ 29 E &e=v[x][i[x]]; 30 if(!e.y||l[e.x]!=l[x]+1) continue; 31 int d=dfs(e.x,min(e.y,y-ret)); 32 if(!d) continue; 33 ret+=d,e.y-=d,v[e.x][e.z].y+=d; 34 if(ret==y) return ret; 35 } 36 l[x]=-1; 37 return ret; 38 } 39 int dinic(){ 40 int ans=0; 41 while(1){ 42 bfs(); 43 if(l[t]==-1) return ans; 44 memset(i,0,sizeof(i)); 45 ans+=dfs(s,orz); 46 } 47 } 48 }_,f; 49 int n,m,ss,tt,s[11000],t[11000],l[11000],r[11000],S[205],T[205],res,rec[11000]; 50 int main(){ 51 scanf("%d%d%d%d",&n,&m,&ss,&tt); 52 _.n=_.t=n+2,_.s=n+1; 53 for(int i=1;i<=m;++i){ 54 scanf("%d%d%d%d",s+i,t+i,l+i,r+i); 55 if(l[i]>r[i]){ 56 puts("please go home to sleep"); 57 return 0; 58 } 59 rec[i]=_.v[t[i]].size(); 60 _.add(s[i],t[i],r[i]-l[i]); 61 S[t[i]]+=l[i],T[s[i]]+=l[i],res+=l[i]; 62 } 63 for(int i=1;i<=n;++i)_.add(_.s,i,S[i]),_.add(i,_.t,T[i]); 64 _.add(tt,ss,orz); 65 res-=_.dinic(); 66 if(res){ 67 puts("please go home to sleep"); 68 return 0; 69 } 70 for(int i=0;i<_.v[ss].size();++i)if(_.v[ss][i].x==tt)res=_.v[ss][i].y; 71 f.n=n,f.s=ss,f.t=tt; 72 for(int i=1;i<=m;++i){ 73 int o=_.v[t[i]][rec[i]].y; 74 E X,Y; 75 X.x=t[i],X.y=r[i]-l[i]-o,X.z=f.v[t[i]].size(); 76 Y.x=s[i],Y.y=o,Y.z=f.v[s[i]].size(); 77 f.v[s[i]].pb(X),f.v[t[i]].pb(Y); 78 } 79 printf("%d ",res+f.dinic()); 80 return 0; 81 }
有源汇上下界最小流
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 2147483647 6 using namespace std; 7 struct E{int x,y,z;}; 8 struct F{ 9 int n,s,t,l[50010],i[50010],q[50010],ql,qr; 10 vector<E> v[50010]; 11 void add(int x,int y,int z){ 12 E X,Y; 13 X.x=y,X.y=z,X.z=v[y].size(); 14 Y.x=x,Y.y=0,Y.z=v[x].size(); 15 v[x].pb(X),v[y].pb(Y); 16 } 17 void bfs(){ 18 memset(l,-1,sizeof(l)); 19 l[q[qr=1]=s]=0; 20 for(ql=1;ql<=qr;++ql){ 21 int x=q[ql]; 22 for(int i=0;i<v[x].size();++i)if(l[v[x][i].x]==-1&&v[x][i].y)l[q[++qr]=v[x][i].x]=l[x]+1; 23 } 24 } 25 int dfs(int x,int y){ 26 if(x==t) return y; 27 int ret=0; 28 for(;i[x]<v[x].size();++i[x]){ 29 E &e=v[x][i[x]]; 30 if(!e.y||l[e.x]!=l[x]+1) continue; 31 int d=dfs(e.x,min(e.y,y-ret)); 32 if(!d) continue; 33 ret+=d,e.y-=d,v[e.x][e.z].y+=d; 34 if(ret==y) return ret; 35 } 36 l[x]=-1; 37 return ret; 38 } 39 int dinic(){ 40 int ans=0; 41 while(1){ 42 bfs(); 43 if(l[t]==-1) return ans; 44 memset(i,0,sizeof(i)); 45 ans+=dfs(s,orz); 46 } 47 } 48 }_,f; 49 int n,m,ss,tt,s[125010],t[125010],l[125010],r[125010],S[50010],T[50010],res,rec[125010]; 50 int main(){ 51 scanf("%d%d%d%d",&n,&m,&ss,&tt); 52 _.n=_.t=n+2,_.s=n+1; 53 for(int i=1;i<=m;++i){ 54 scanf("%d%d%d%d",s+i,t+i,l+i,r+i); 55 if(l[i]>r[i]){ 56 puts("please go home to sleep"); 57 return 0; 58 } 59 rec[i]=_.v[t[i]].size(); 60 _.add(s[i],t[i],r[i]-l[i]); 61 S[t[i]]+=l[i],T[s[i]]+=l[i],res+=l[i]; 62 } 63 for(int i=1;i<=n;++i)_.add(_.s,i,S[i]),_.add(i,_.t,T[i]); 64 _.add(tt,ss,orz); 65 res-=_.dinic(); 66 if(res){ 67 puts("please go home to sleep"); 68 return 0; 69 } 70 for(int i=0;i<_.v[ss].size();++i)if(_.v[ss][i].x==tt)res=_.v[ss][i].y; 71 f.n=n,f.s=tt,f.t=ss; 72 for(int i=1;i<=m;++i){ 73 int o=_.v[t[i]][rec[i]].y; 74 E X,Y; 75 X.x=t[i],X.y=r[i]-l[i]-o,X.z=f.v[t[i]].size(); 76 Y.x=s[i],Y.y=o,Y.z=f.v[s[i]].size(); 77 f.v[s[i]].pb(X),f.v[t[i]].pb(Y); 78 } 79 printf("%d ",res-f.dinic()); 80 return 0; 81 }
KDT
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 struct T{int l,r,x[2],d[2],k[2],s,v;}t[200005]; 8 int N,n,ans,D,r=1,X[2],Y[2]; 9 bool cmp(T x,T y){return x.k[D]==y.k[D]?x.k[D^1]<y.k[D^1]:x.k[D]<y.k[D];} 10 void upd(int k){ 11 t[k].x[0]=t[k].d[0]=t[k].k[0]; 12 t[k].x[1]=t[k].d[1]=t[k].k[1]; 13 t[k].s=t[k].v; 14 if(t[k].l){ 15 t[k].s+=t[t[k].l].s; 16 if(t[t[k].l].x[0]<t[k].x[0])t[k].x[0]=t[t[k].l].x[0]; 17 if(t[t[k].l].x[1]<t[k].x[1])t[k].x[1]=t[t[k].l].x[1]; 18 if(t[t[k].l].d[0]>t[k].d[0])t[k].d[0]=t[t[k].l].d[0]; 19 if(t[t[k].l].d[1]>t[k].d[1])t[k].d[1]=t[t[k].l].d[1]; 20 } 21 if(t[k].r){ 22 t[k].s+=t[t[k].r].s; 23 if(t[t[k].r].x[0]<t[k].x[0])t[k].x[0]=t[t[k].r].x[0]; 24 if(t[t[k].r].x[1]<t[k].x[1])t[k].x[1]=t[t[k].r].x[1]; 25 if(t[t[k].r].d[0]>t[k].d[0])t[k].d[0]=t[t[k].r].d[0]; 26 if(t[t[k].r].d[1]>t[k].d[1])t[k].d[1]=t[t[k].r].d[1]; 27 } 28 } 29 int build(int l,int r,int d){ 30 int m=(l+r)>>1; 31 D=d; 32 nth_element(t+l+1,t+m+1,t+r+1,cmp); 33 if(l<m)t[m].l=build(l,m-1,d^1); 34 if(m<r)t[m].r=build(m+1,r,d^1); 35 upd(m); 36 return m; 37 } 38 void ins(int k){ 39 int o=r,d=0; 40 while(1){ 41 t[o].s+=t[k].v; 42 if(t[k].x[0]<t[o].x[0])t[o].x[0]=t[k].x[0]; 43 if(t[k].x[1]<t[o].x[1])t[o].x[1]=t[k].x[1]; 44 if(t[k].d[0]>t[o].d[0])t[o].d[0]=t[k].d[0]; 45 if(t[k].d[1]>t[o].d[1])t[o].d[1]=t[k].d[1]; 46 if(mp(t[k].k[d],t[k].k[d^1])<mp(t[o].k[d],t[o].k[d^1])){ 47 if(!t[o].l){t[o].l=k;return;} 48 else o=t[o].l; 49 } 50 else{ 51 if(!t[o].r){t[o].r=k;return;} 52 else o=t[o].r; 53 } 54 d^=1; 55 } 56 } 57 void ask(int k){ 58 if(t[k].x[0]>Y[0]||t[k].d[0]<X[0]||t[k].x[1]>Y[1]||t[k].d[1]<X[1]) return; 59 if(t[k].x[0]>=X[0]&&t[k].d[0]<=Y[0]&&t[k].x[1]>=X[1]&&t[k].d[1]<=Y[1]){ 60 ans+=t[k].s; 61 return; 62 } 63 if(t[k].k[0]>=X[0]&&t[k].k[0]<=Y[0]&&t[k].k[1]>=X[1]&&t[k].k[1]<=Y[1])ans+=t[k].v; 64 if(t[k].l)ask(t[k].l); 65 if(t[k].r)ask(t[k].r); 66 } 67 int main(){ 68 scanf("%d",&N); 69 while(1){ 70 int T; 71 scanf("%d",&T); 72 if(T==1){ 73 ++n; 74 scanf("%d%d%d",&t[n].k[0],&t[n].k[1],&t[n].v); 75 t[n].k[0]^=ans,t[n].k[1]^=ans,t[n].v^=ans; 76 upd(n); 77 if(!(n&16383)){ 78 for(int i=1;i<n;++i)t[i].l=t[i].r=0,upd(i); 79 r=build(1,n,0); 80 } 81 else if(n>1)ins(n); 82 } 83 else if(T==2){ 84 scanf("%d%d%d%d",X,X+1,Y,Y+1); 85 X[0]^=ans,X[1]^=ans,Y[0]^=ans,Y[1]^=ans; 86 ans=0; 87 ask(r); 88 printf("%d ",ans); 89 } 90 else break; 91 } 92 return 0; 93 }
判素数
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 ll x; 8 ll mul(ll x,ll y,ll n){ 9 if(x<y)swap(x,y); 10 ll ans=0; 11 while(y){ 12 if(y&1){ 13 ans+=x; 14 if(ans>=n)ans-=n; 15 } 16 y>>=1; 17 x+=x; 18 if(x>=n)x-=n; 19 } 20 return ans; 21 } 22 ll fp(ll x,ll k,ll n){ 23 ll ans=1; 24 while(k){ 25 if(k&1)ans=mul(ans,x,n); 26 k>>=1,x=mul(x,x,n); 27 } 28 return ans; 29 } 30 bool ch(ll x,ll k){ 31 ll e=(x-1)/2; 32 while(1){ 33 ll o=fp(k,e,x); 34 if(o==x-1) return 1; 35 if(o==1){ 36 if(e%2==0)e/=2; 37 else return 1; 38 } 39 else return 0; 40 } 41 } 42 bool ok(ll x){ 43 if(!ch(x,2)) return 0; 44 if(!ch(x,3)) return 0; 45 if(!ch(x,5)) return 0; 46 if(!ch(x,7)) return 0; 47 if(!ch(x,11)) return 0; 48 if(!ch(x,13)) return 0; 49 if(!ch(x,17)) return 0; 50 if(!ch(x,19)) return 0; 51 if(!ch(x,101)) return 0; 52 return 1; 53 } 54 int f[1000005],p[30],k; 55 int main(){ 56 f[1]=1; 57 for(int i=2;i<=1000000;++i){ 58 if(f[i]) continue; 59 for(int j=i*2;j<=1000000;j+=i)f[j]=1; 60 } 61 for(int i=2;i<=100;++i)if(!f[i])p[++k]=i; 62 while(cin>>x){ 63 if(x<=1000000){ 64 if(f[x])puts("N"); 65 else puts("Y"); 66 } 67 else{ 68 bool _=1; 69 for(int i=1;i<=k;++i)if(x%p[i]==0)_=0,i=k; 70 if(!_)puts("N"); 71 else if(ok(x))puts("Y"); 72 else puts("N"); 73 } 74 } 75 return 0; 76 }
Lyndon 分解
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 string s; 8 int n,a[1100000],l[1100000],m; 9 int main(){ 10 ios::sync_with_stdio(0); 11 cin>>s; 12 n=s.size(); 13 for(int i=1;i<=n;++i)a[i]=s[i-1]; 14 for(int i=1;i<=n;){ 15 int j=i,k=i+1; 16 while(k<=n&&a[j]<=a[k]){ 17 if(a[j]<a[k])j=i; 18 else ++j; 19 ++k; 20 } 21 while(i<=j)i+=k-j,l[++m]=i-1; 22 } 23 for(int i=1;i<m;++i)printf("%d ",l[i]); 24 printf("%d ",l[m]); 25 return 0; 26 }
fwt
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 998244353 6 using namespace std; 7 int n,m,a[131111],b[131111]; 8 struct S{ 9 int a[131111],b[131111],c[131111]; 10 void mul(){ 11 for(int i=0;i<n;++i)c[i]=a[i]*1ll*b[i]%orz; 12 } 13 void out(){ 14 for(int i=0;i<n-1;++i)printf("%d ",c[i]); 15 printf("%d ",c[n-1]); 16 } 17 }_o,_a,_x; 18 void fwt_or(int *a){ 19 for(int i=2;i<=n;i<<=1){ 20 for(int j=0;j<n;j+=i){ 21 for(int k=0;k<(i>>1);++k){ 22 int l=j+k,r=l+(i>>1); 23 a[r]+=a[l]; 24 if(a[r]>=orz)a[r]-=orz; 25 } 26 } 27 } 28 } 29 void ifwt_or(int *a){ 30 for(int i=2;i<=n;i<<=1){ 31 for(int j=0;j<n;j+=i){ 32 for(int k=0;k<(i>>1);++k){ 33 int l=j+k,r=l+(i>>1); 34 a[r]+=orz-a[l]; 35 if(a[r]>=orz)a[r]-=orz; 36 } 37 } 38 } 39 } 40 void fwt_and(int *a){ 41 for(int i=2;i<=n;i<<=1){ 42 for(int j=0;j<n;j+=i){ 43 for(int k=0;k<(i>>1);++k){ 44 int l=j+k,r=l+(i>>1); 45 a[l]+=a[r]; 46 if(a[l]>=orz)a[l]-=orz; 47 } 48 } 49 } 50 } 51 void ifwt_and(int *a){ 52 for(int i=2;i<=n;i<<=1){ 53 for(int j=0;j<n;j+=i){ 54 for(int k=0;k<(i>>1);++k){ 55 int l=j+k,r=l+(i>>1); 56 a[l]+=orz-a[r]; 57 if(a[l]>=orz)a[l]-=orz; 58 } 59 } 60 } 61 } 62 void fwt_xor(int *a){ 63 for(int i=2;i<=n;i<<=1){ 64 for(int j=0;j<n;j+=i){ 65 for(int k=0;k<(i>>1);++k){ 66 int l=j+k,r=l+(i>>1),x=a[l]+a[r],y=a[l]+orz-a[r]; 67 a[l]=x,a[r]=y; 68 if(a[l]>=orz)a[l]-=orz; 69 if(a[r]>=orz)a[r]-=orz; 70 } 71 } 72 } 73 } 74 void ifwt_xor(int *a){ 75 for(int i=2;i<=n;i<<=1){ 76 for(int j=0;j<n;j+=i){ 77 for(int k=0;k<(i>>1);++k){ 78 int l=j+k,r=l+(i>>1),x=a[l]+a[r],y=a[l]+orz-a[r]; 79 a[l]=x,a[r]=y; 80 if(a[l]>=orz)a[l]-=orz; 81 if(a[r]>=orz)a[r]-=orz; 82 if(a[l]&1)a[l]+=orz; 83 if(a[r]&1)a[r]+=orz; 84 a[l]>>=1,a[r]>>=1; 85 } 86 } 87 } 88 } 89 int main(){ 90 scanf("%d",&m); 91 for(int i=0;i<m;++i)scanf("%d",a+i),_o.a[i]=_a.a[i]=_x.a[i]=a[i]; 92 for(int i=0;i<m;++i)scanf("%d",b+i),_o.b[i]=_a.b[i]=_x.b[i]=b[i]; 93 n=1; 94 while(n<m)n<<=1; 95 fwt_or(_o.a),fwt_or(_o.b),fwt_and(_a.a),fwt_and(_a.b),fwt_xor(_x.a),fwt_xor(_x.b); 96 _o.mul(),_a.mul(),_x.mul(); 97 ifwt_or(_o.c),ifwt_and(_a.c),ifwt_xor(_x.c); 98 _o.out(),_a.out(),_x.out(); 99 return 0; 100 }
后缀自动机
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int n,a[5000005]; 8 int ch[10000005][26],nx[10000005],mx[10000005],la=1,_=1; 9 ll res,ans; 10 int main(){ 11 char in=getchar(); 12 while(in>96)a[++n]=in-97,in=getchar(); 13 for(int i=1;i<=n;++i){ 14 int x=++_,y=la,c=a[i]; 15 mx[x]=mx[y]+1; 16 for(;y&&!ch[y][c];y=nx[y])ch[y][c]=x; 17 if(!y)nx[x]=1,res+=mx[x]; 18 else if(mx[ch[y][c]]==mx[y]+1)nx[x]=ch[y][c],res+=mx[x]-mx[nx[x]]; 19 else{ 20 int p=++_,o=ch[y][c]; 21 mx[p]=mx[y]+1; 22 nx[p]=nx[o],nx[o]=nx[x]=p; 23 res+=mx[x]-mx[p]; 24 memcpy(ch[p],ch[o],sizeof(ch[o])); 25 for(;y&&ch[y][c]==o;y=nx[y])ch[y][c]=p; 26 } 27 la=x,ans^=res; 28 } 29 printf("%lld ",ans); 30 return 0; 31 }
回文自动机
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define mp make_pair 5 #define orz 1000000007 6 using namespace std; 7 int n,a[300005],len[300005],cnt[300005],ch[300005][26],_,la,nx[300005]; 8 ll ans; 9 int ne(int l){ 10 len[_]=l,cnt[_]=0; 11 return _++; 12 } 13 int get(int x,int y){ 14 while(a[y-len[x]-1]!=a[y])x=nx[x]; 15 return x; 16 } 17 int main(){ 18 char in=getchar(); 19 while(in>96)a[++n]=in-97,in=getchar(); 20 a[0]=-1,ne(0),ne(-1),la=0,nx[0]=1; 21 for(int i=1;i<=n;++i){ 22 int o=get(la,i),k=a[i]; 23 if(!ch[o][k]){ 24 int p=ne(len[o]+2); 25 nx[p]=ch[get(nx[o],i)][k]; 26 ch[o][k]=p; 27 } 28 ++cnt[la=ch[o][k]]; 29 } 30 for(int i=_-1;i>1;--i)cnt[nx[i]]+=cnt[i],ans=max(ans,len[i]*1ll*cnt[i]); 31 printf("%lld ",ans); 32 return 0; 33 }