板子集合
贴一些不熟练的板子
#include<cstdio> const int mod=998244353,maxn=1<<18; int T,n; long long g[maxn],f[maxn],gr[maxn],w[2][maxn+1]; long long power(long long a,long long b){long long ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;} void fft(long long a[],int tt,int op) { int i,j,k,l; static long long aa[maxn]; for(i=0;i<tt;i++) { for(l=0,j=i,k=1;k<tt;k<<=1,j>>=1)l=(l<<1)+(j&1); aa[l]=a[i]; } for(i=2;i<=tt;i<<=1) for(j=0;j<tt;j+=i) for(k=0;k<(i>>1);k++) { long long u=aa[j+k],v=aa[j+k+(i>>1)]*w[op][maxn/i*k]%mod; aa[j+k]=(u+v)%mod; aa[j+k+(i>>1)]=(u-v+mod)%mod; } if(op) { int tr=power(tt,mod-2); for(i=0;i<tt;i++)aa[i]=aa[i]*tr%mod; } for(i=0;i<tt;i++)a[i]=aa[i]; } void inv(long long a[],long long ar[],int t) { int i,j,k; static long long aa[maxn]; if(t==1){ar[0]=power(a[0],mod-2);return;} inv(a,ar,t>>1); for(k=1;k<(t<<1);k<<=1); for(j=0;j<t;j++)aa[j]=a[j];for(j=t;j<k;j++)aa[j]=0; fft(ar,k,0);fft(aa,k,0); for(j=0;j<k;j++)aa[j]=(2-ar[j]*aa[j]%mod+mod)%mod; for(j=0;j<k;j++)ar[j]=ar[j]*aa[j]%mod; fft(ar,k,1); for(i=t;i<k;i++)ar[i]=0; } int main() { int i,j,k; w[0][0]=1; long long tt=power(3,(mod-1)/maxn); for(i=1;i<=maxn;i++)w[0][i]=w[0][i-1]*tt%mod; for(i=0;i<=maxn;i++)w[1][i]=w[0][maxn-i]; g[0]=1; for(i=1;i<=maxn;i++)g[i]=g[i-1]*i%mod; inv(g,gr,maxn/2); for(i=0;i<=maxn/2;i++)f[i]=(mod-gr[i])%mod; f[0]++; scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%lld\n",f[n]); } return 0; }
#include<cstdio> #include<cstring> char s[100011]; int n,sa[200001],rank[200001],tsa[200001],trank[200001],h[200001]; int a[200001]; int main() { int i,j,k,p; scanf("%s",s+1);n=strlen(s+1); for(i=1;i<=n;i++)trank[i]=s[i]-'a'; for(i=1;i<=n;i++)a[trank[i]]++; for(i=1;i<26;i++)a[i]+=a[i-1]; for(i=n;i>0;i--)sa[a[trank[i]]--]=i; rank[sa[1]]=p=1; for(i=2;i<=n;i++) { if(trank[sa[i]]!=trank[sa[i-1]])p++; rank[sa[i]]=p; } for(i=1;i<=n;i<<=1) { memset(a,0,sizeof(a)); for(j=1;j<=n;j++)a[rank[j+i]]++; for(j=1;j<=p;j++)a[j]+=a[j-1]; for(j=n;j>0;j--)tsa[a[rank[j+i]]--]=j; memset(a,0,sizeof(a)); for(j=1;j<=n;j++)a[rank[j]]++; for(j=1;j<=p;j++)a[j]+=a[j-1]; for(j=n;j>0;j--)sa[a[rank[tsa[j]]]--]=tsa[j]; trank[sa[1]]=p=1; for(j=2;j<=n;j++) { if(rank[sa[j]]!=rank[sa[j-1]]||rank[sa[j]+i]!=rank[sa[j-1]+i])p++; trank[sa[j]]=p; } for(j=1;j<=n;j++)rank[j]=trank[j]; } for(i=1,j=0;i<=n;i++) { if(rank[i]==1)continue; while(s[i+j]==s[sa[rank[i]-1]+j])j++; h[rank[i]]=j; if(j>0)j--; } for(i=1;i<=n;i++)printf("%d ",sa[i]);puts(""); for(i=2;i<=n;i++)printf("%d ",h[i]);puts(""); return 0; }
#include<cstdio> int n,c; int a[100001]; int head[100001],end[200001],next[200001],tp=0; int deg[100001]; int son[11][4000001],fail[4000001],len[4000001],last=1,tt=1; long long gs[4000001]; void add(int ch) { int i,j,k; if(son[ch][last]) { i=last;j=son[ch][last]; if(len[j]==len[i]+1)last=j;else { ++tt;len[tt]=len[i]+1;for(k=0;k<c;k++)son[k][tt]=son[k][j]; fail[tt]=fail[j]; for(;i&&son[ch][i]==j;i=fail[i])son[ch][i]=tt; fail[j]=tt;last=tt; } } else { int cur=++tt;len[tt]=len[last]+1; for(i=last;i&&!son[ch][i];i=fail[i])son[ch][i]=tt; if(!i)fail[tt]=1;else { j=son[ch][i]; if(len[i]+1==len[j])fail[tt]=j;else { ++tt;len[tt]=len[i]+1;for(k=0;k<c;k++)son[k][tt]=son[k][j]; fail[tt]=fail[j]; for(;i&&son[ch][i]==j;i=fail[i])son[ch][i]=tt; fail[j]=tt;fail[cur]=tt; } } last=cur; } } void dfs(int p,int d) { int i,j,k; add(a[p]); int t=last; for(i=head[p];i;i=next[i])if(end[i]!=d) { dfs(end[i],p);last=t; } } void dfs2(int p) { int i,j,k; if(gs[p])return; //printf("p=%d\n",p); for(i=0;i<c;i++)if(son[i][p]){dfs2(son[i][p]);gs[p]+=gs[son[i][p]];} gs[p]++; } int main() { int i,j,k; scanf("%d%d",&n,&c); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); next[++tp]=head[x];head[x]=tp;end[tp]=y; next[++tp]=head[y];head[y]=tp;end[tp]=x; deg[x]++;deg[y]++; } for(i=1;i<=n;i++)if(deg[i]==1){last=1;dfs(i,i);} //puts("ok"); dfs2(1); printf("%lld\n",gs[1]-1); return 0; }
#include<cstdio> #include<algorithm> int rev[150001],mx[150001],c[150001],dad[150001],son[150001][2]; int st[150001],tp=0; int isroot(int p){return son[dad[p]][0]!=p&&son[dad[p]][1]!=p;} void reverse(int p) { rev[p]^=1;int t=son[p][0];son[p][0]=son[p][1];son[p][1]=t; rev[son[p][0]]^=1;rev[son[p][1]]^=1; } void upd(int p) { mx[p]=p; if(c[mx[son[p][0]]]>c[mx[p]])mx[p]=mx[son[p][0]]; if(c[mx[son[p][1]]]>c[mx[p]])mx[p]=mx[son[p][1]]; } void rot(int p) { int d=dad[p],dd=dad[dad[p]]; int t=son[d][1]==p; if(!isroot(d))son[dd][son[dd][1]==d]=p; son[d][t]=son[p][!t];son[p][!t]=d; dad[p]=dd;dad[d]=p;dad[son[d][t]]=d; upd(d);upd(p); printf("p=%d d=%d\n",p,d); } void splay(int p) { int i; tp=0;st[++tp]=p; for(i=p;!isroot(i);i=dad[i])st[++tp]=dad[i]; while(tp){if(rev[st[tp]])reverse(st[tp]);tp--;} while(!isroot(p)) { if(!isroot(dad[p])) { if((son[dad[p]][0]==p)^(son[dad[dad[p]]][0]==dad[p]))rot(p);else rot(dad[p]); } upd(p);rot(p); } } void access(int p){int i=0;for(;p;p=dad[p]){splay(p);son[p][1]=i;i=p;upd(p);}} void makeroot(int p){access(p);splay(p);rev[p]^=1;} void link(int x,int y){makeroot(x);dad[x]=y;} void cut(int x,int y){makeroot(x);access(y);splay(y);son[y][0]=0;dad[x]=0;} int fmax(int x,int y){makeroot(x);access(y);splay(y);return mx[y];} int n,m; int ans=1<<30; struct mjj{int x,y,a,b;}a[100001]; int fa[50001]; int find(int p){return p==fa[p]?p:fa[p]=find(fa[p]);} int cmp(mjj a,mjj b){return a.a<b.a;} int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b); std::sort(a+1,a+m+1,cmp); for(i=1;i<=n;i++)fa[i]=i; for(i=1;i<=m;i++) { if(find(a[i].x)!=find(a[i].y)) { fa[fa[a[i].x]]=fa[a[i].y]; c[n+i]=a[i].b;mx[n+i]=n+i; link(n+i,a[i].x);link(n+i,a[i].y); } else { int t=fmax(a[i].x,a[i].y); if(c[t]>a[i].b) { cut(t,a[t-n].x);cut(t,a[t-n].y); c[n+i]=a[i].b;mx[n+i]=n+i; link(n+i,a[i].x);link(n+i,a[i].y); } } if(find(1)==find(n)) { int t=fmax(1,n); if(c[t]+a[i].a<ans)ans=c[t]+a[i].a; } } if(ans==1<<30)puts("-1");else printf("%d\n",ans); return 0; }
#include<cstdio> #include<cmath> #include<cstdlib> #define double long double const double eps=1e-9; int n,m,ta; double c[21]; double a[21][42]; int b[21],wz[42]; double x[42]; void pivot(int fr,int to,int mgs,int gs) { int i,j,k; double t=a[to][fr]; for(j=0;j<=gs;j++)a[to][j]/=-t; a[to][b[to]]=1/t;a[to][fr]=0; wz[b[to]]=0;b[to]=fr;wz[fr]=to; for(i=0;i<=mgs;i++)if(i!=to) { double t=a[i][fr];a[i][fr]=0; for(j=0;j<=gs;j++)a[i][j]+=t*a[to][j]; } } double solve(int mgs,int gs) { int i,j,k; while(1) { //for(i=0;i<=mgs;i++) //{for(j=0;j<=gs;j++)printf("%lf ",a[i][j]);puts("");}puts(""); for(i=1,j=0;i<=gs;i++)if(!wz[i]&&a[0][i]>eps&&(!j||(rand()&1)))j=i; if(!j)return a[0][0]; double t=1.0/0;k=0; for(i=1;i<=mgs;i++)if(a[i][j]<-eps) { if(-a[i][0]/a[i][j]<t){t=-a[i][0]/a[i][j];k=i;} } if(k==0)return 1.0/0; pivot(j,k,mgs,gs); } } int main() { int i,j,k; scanf("%d%d%d",&n,&m,&ta); for(i=1;i<=n;i++)scanf("%Lf",&c[i]); for(i=1;i<=m;i++) { for(j=1;j<=n;j++){scanf("%Lf",&a[i][j]);a[i][j]=-a[i][j];} scanf("%Lf",&a[i][0]); b[i]=n+i;wz[n+i]=i; } for(i=1;i<=m;i++)a[i][n+m+1]=1; a[0][n+m+1]=-1; j=1; for(i=2;i<=m;i++)if(a[i][0]<a[j][0])j=i; if(a[j][0]<-eps)pivot(n+m+1,j,m,n+m+1); double ans=solve(m,n+m+1); if(ans<-eps){puts("Infeasible");return 0;} if(wz[n+m+1]) { for(i=1;i<=n+m;i++)if(!wz[i]&&fabs(a[0][i])>eps) { pivot(i,wz[n+m+1],m,n+m+1); break; } } for(i=0;i<=n+m;i++)a[0][i]=0; for(i=1;i<=n;i++) { if(!wz[i])a[0][i]+=c[i];else { for(j=0;j<=n+m;j++)a[0][j]+=c[i]*a[wz[i]][j]; } } for(i=0;i<=m;i++)a[i][n+m+1]=0; ans=solve(m,n+m); if(ans<=1e100) { printf("%.10Lf\n",a[0][0]); if(ta) { for(i=1;i<=m;i++)x[b[i]]=a[i][0]; for(i=1;i<=n;i++)printf("%.10Lf ",x[i]);puts(""); } } else puts("Unbounded"); return 0; }
#include<cstdio> #include<cstring> #include<cstdlib> int n,m; int head[501],end[250001],next[250001],tp=-1; int pp[501],vis[501],a[501],dad[501],pre[501],vis2[501],tim; int ans; int q[501],hh=1,tt=0; int find(int p){return p==dad[p]?p:dad[p]=find(dad[p]);} int lca(int x,int y) { tim++; for(;;x=pre[pp[x]]) { x=find(x); vis2[x]=tim; //printf("x=%d\n",x); if(!pp[x])break; } //printf("tim=%d\n",tim); //puts("ok3"); for(;;y=pre[pp[y]]) { y=find(y); if(vis2[y]==tim)break; //printf("y=%d vis2[y]=%d\n",y,vis2[y]); //system("pause"); } return y; } void join(int x,int y) { for(;x!=y;x=pre[pp[x]]) { int t=pp[x]; if(find(pre[t])!=find(y))pre[pre[t]]=t; if(vis[t]==2){vis[t]=1;q[++tt]=t;} if(vis[pre[t]]==2){vis[pre[t]]=1;q[++tt]=pre[t];} dad[find(t)]=find(pre[t]); dad[find(x)]=find(t); } } int bfs(int p) { int i,j,k; memset(vis,0,sizeof(vis));memset(a,0,sizeof(a)); for(i=1;i<=n;i++)dad[i]=i; hh=1;tt=0; q[++tt]=p;vis[p]=1; while(hh<=tt) { //printf("q[hh]=%d\n",q[hh]); for(i=head[q[hh]];i>=0;i=next[i]) { //printf("end[i]=%d\n",end[i]); if(find(end[i])==find(q[hh])||end[i]==pp[q[hh]])continue; if(!vis[end[i]]) { if(pp[end[i]]) { vis[end[i]]=2;vis[pp[end[i]]]=1;pre[end[i]]=q[hh]; q[++tt]=pp[end[i]]; } else { //puts("ok"); pre[end[i]]=q[hh]; for(j=end[i];pre[j]!=p;) { k=pp[pre[j]]; pp[j]=pre[j];pp[pre[j]]=j; j=k; } pp[j]=p;pp[p]=j; return 1; } } else if(vis[end[i]]==1) { //puts("ok2"); int t=lca(q[hh],end[i]); if(find(q[hh])!=find(t))pre[q[hh]]=end[i]; if(find(end[i])!=find(t))pre[end[i]]=q[hh]; join(q[hh],t); join(end[i],t); } } hh++; } return 0; } int main() { int i,j,k; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); next[++tp]=head[x];head[x]=tp;end[tp]=y; next[++tp]=head[y];head[y]=tp;end[tp]=x; } for(i=1;i<=n;i++)if(!pp[i]) { ans+=bfs(i); } printf("%d\n",ans); for(i=1;i<=n;i++)printf("%d ",pp[i]); return 0; }
#include<cstdio> long long n; int mod; int p[100001],tp=0,cnt[100001],pc[100001]; long long power(long long a,long long b,long long mod){long long ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;} long long fac(long long a,int q,long long &cs) { long long s=1; long long ans=1; long long ss=a/pc[q],rm=a%pc[q]; int i; if(a==0)return 1; for(i=1;i<=pc[q];i++)if(i%p[q]!=0)s=s*i%pc[q]; ans=power(s,ss,pc[q]); for(i=1;i<=rm;i++)if(i%p[q]!=0)ans=ans*i%pc[q]; ans=ans*fac(a/p[q],q,cs)%pc[q]; cs+=a/p[q]; return ans; } long long exgcd(long long a,long long b,long long &x,long long &y) { if(b==0){x=1;y=0;return a;} long long r=exgcd(b,a%b,x,y); long long t=x;x=y;y=t-a/b*y; return r; } long long C(long long a,long long b) { int i; long long ans=0; for(i=1;i<=tp;i++) { long long ta=0,tb=0,tab=0; long long aa=fac(a,i,ta),ab=fac(b,i,tb),aab=fac(a-b,i,tab); long long nb,nab,tt; exgcd(ab,pc[i],nb,tt);while(nb<0)nb+=pc[i]; exgcd(aab,pc[i],nab,tt);while(nab<0)nab+=pc[i]; long long tans=aa*nb%pc[i]*nab%pc[i]*power(p[i],ta-tb-tab,pc[i])%pc[i]; long long nans; exgcd(mod/pc[i],pc[i],nans,tt);while(nans<0)nans+=pc[i]; ans=(ans+tans*nans%mod*(mod/pc[i])%mod)%mod; } return ans; } int main() { int i,j,k; //freopen("T3.in","r",stdin);freopen("T3.out","w",stdout); scanf("%lld%d",&n,&mod); n--; if(n==0){puts("1");return 0;} long long t=mod; for(i=2;i*i<=mod;i++)if(t%i==0) { p[++tp]=i;pc[tp]=1; while(t%i==0){cnt[tp]++;pc[tp]*=i;t/=i;} } if(t>1){p[++tp]=t;cnt[tp]=1;pc[tp]=t;} printf("%lld\n",(C(2*n,n)-C(2*n,n-1)+mod)%mod); return 0; }