板子集合

贴一些不熟练的板子

#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;
}