板子集合

hhw posted @ 2016年3月15日 08:27 in 代码 with tags 代码 模板 , 1464 阅读

贴一些不熟练的板子

 

#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;
}
Avatar_small
SSO login 说:
2022年8月04日 02:12

SSO stands for Single Sign On and SSO Rajasthan for any citizen to create their digital identity. According to their official website, more than 18672702 identities have been create from their official website. SSO login There are different benefits of being a part of this online platform out of which the primary one is to be under the Jan Aadhaar scheme and benefits. Along with that you can also get benefits from schemes such as Bhamashah but before you do, you have to create your account and in the below guide we have explained the exact steps you need to follow, and if any queries, you may contact SSO customer care.

Avatar_small
AP SSC Social Model 说:
2022年9月19日 00:34

Social Study is most important students to all students of AP 10th Class, here we have provided the study material with solved question bank for all government and private school TM, EM, UM and HM students in chapter wise from past years old exams and we have provided the AP 10th Social Model Paper 2023 Pdf suggested by subject experts. AP SSC Social Model Paper All BSEAP 10th class regular and private course students can follow the list of chapters under SSC Social Study to practice study material with previous question bank to get a better score in summative assessment (SA) and formative assessment (FA) SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 along with Assignments exams previously called Unit Test-1, Unit Test-2, Unit Test-3, Unit Test-4 and Three Months.

Avatar_small
How to Apply Tamil N 说:
2022年11月15日 01:20

Tamil Nadu state government works to improve residents’ lives by providing permanent and reliable help. The government offers education programs through various programs and schemes. How to Apply Tamil Nadu First Graduate Certificate 2023 TN citizens can avail scholarship programs for different levels. Education helps eradicate illiteracy and improve the economic status of both families and the state.

Avatar_small
Exam Pattern 2024 说:
2023年2月13日 16:00

Board of Secondary Education has deferred the board Exam should be held from May 2024. The candidates can check the Board blueprint Papers from true site. Exam Pattern 2024 The Question Paper 2024 will likewise be reported on class students can take note of the total Exam Pattern 2024. Download the Board Model Paper and Question Paper 2024 as indicated by the 12th Class Model Paper 2024 educational board.

Avatar_small
bravotv.com/link act 说:
2023年7月11日 23:17

Bravo TV is one of the most famous pay television networks in the United States. This channel is one of the NBC Universal families and acts as an alternative for Comcast. bravotv.com/link activate code Bravo TV broadcasts worldwide and mostly wants to focus on movies and events. Activation Code is the password for activating the entertainment service. You will be capable of activating your Smart TV using this method.

Avatar_small
jnanabhumiap.in 说:
2024年1月27日 22:43

JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic jnanabhumiap.in which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter