首页 > 代码库 > bzoj3491: PA2007 Subsets
bzoj3491: PA2007 Subsets
Description
有一个集合U={1，2，…，n），要从中选择k个元素作为一个子集A。
若a∈A，则要有a*X不属于A，x是一个给定的数。
求可选方案对M取模后的值。
1< = N< = 10^18,2< = m< = 1000000,0< = K< = 1000,2< = x< = 10。
Input
第一行输入N,M,K,X
Output
如题
将不能共存的数连边，每个联通块都是一条链，计算出每个长度的链的条数，以及每个长度的链上取0~k个数的方案数，卷积可得答案。时间复杂度$O(klog(k)log(n)log_x(n))$
#include<cstdio>#include<cmath>#include<algorithm>typedef unsigned long long u64;typedef long double ld;const ld pi=std::acos(-1);struct cplx{ ld a,b; cplx(ld x=0,ld y=0):a(x),b(y){} cplx operator+(cplx x){return cplx(a+x.a,b+x.b);} cplx operator-(cplx x){return cplx(a-x.a,b-x.b);} cplx operator*(cplx x){return cplx(a*x.a-b*x.b,a*x.b+b*x.a);} cplx conj(){return cplx(a,-b);}}A[2111],B[2111],E[2][13][1111];u64 n,pwx[77],ts[77];int m,k,x,ppx=0,C[77][77],N,K;int ans[1111],tmp[1111],tmp2[1111],rev[2111];void dft(cplx*a,int t){ for(int i=0;i<N;++i)if(i<rev[i])std::swap(a[i],a[rev[i]]); for(int i=1,z=0;i<N;i<<=1,++z){ cplx*e=E[t][z]; for(int j=0;j<N;j+=i<<1){ cplx*b=a+j,*c=b+i; for(int k=0;k<i;++k){ cplx x=b[k],y=c[k]*e[k]; b[k]=x+y; c[k]=x-y; } } } if(t)for(int i=0;i<N;++i)a[i].a/=N;}void mul(int*a,int*b){ for(int i=0;i<=k;++i)B[i]=cplx(a[i],b[i]); for(int i=k+1;i<N;++i)B[i]=0; dft(B,0); B[N]=B[0]; for(int i=0;i<N;++i){ cplx x=B[i],y=B[N-i].conj(); A[i]=cplx(0,0.25)*(y+x)*(y-x); } dft(A,1); for(int i=0;i<=k;++i)a[i]=((long long)(A[i].a+0.49))%m;}int main(){ scanf("%llu%d%d%d",&n,&m,&k,&x); C[0][0]=1; for(int i=0;i<70;++i){ for(int j=0;j<=i;++j){ (C[i+1][j]+=C[i][j])%=m; (C[i+1][j+1]+=C[i][j])%=m; } } for(pwx[ppx++]=1;(pwx[ppx]=pwx[ppx-1]*x)<=n;++ppx); for(int i=ppx-1;i>=0;--i){ ts[i]=n/pwx[i]; ts[i]-=ts[i]/x; } for(N=2,K=0;N<k*2+5;N<<=1,++K); for(int i=1;i<N;++i)rev[i]=rev[i>>1]>>1|(i&1)<<K; for(int i=1,z=0;i<N;i<<=1,++z){ for(int j=0;j<i;++j){ E[0][z][j]=cplx(cos(j*pi/i),sin(j*pi/i)); E[1][z][j]=E[0][z][j].conj(); } } ans[0]=1; for(int i=0;i<ppx;++i){ ts[i]-=ts[i+1]; for(int j=0;j<=k;++j)tmp[j]=(i+2-j>=0?C[i+2-j][j]:0),tmp2[j]=0; tmp2[0]=1; for(u64 t=ts[i];t;t>>=1,mul(tmp,tmp))if(t&1)mul(tmp2,tmp); mul(ans,tmp2); } printf("%d\n",ans[k]); return 0;}
bzoj3491: PA2007 Subsets
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。