首页 > 代码库 > BZOJ2498 : Xavier is Learning to Count
BZOJ2498 : Xavier is Learning to Count
考虑容斥，通过$Bell(p)$的时间枚举所有等价情况。
对于一种情况，强制了一个等价类里面的数都要相同，其它的可以相同也可以不同。
这方案数显然可以通过多项式乘法求得，乘上容斥系数$(-1)^{p-等价类个数}\ \ \ \ \ \ \ \times(每个等价类大小-1)!之积$。
可以先把那$p$个多项式DFT，然后在点值表示下计算答案，最后再IDFT回来即可。
时间复杂度$O(pn(\log n+Bell(p))$。
#include<cstdio>#include<cmath>#include<algorithm>using namespace std;typedef long double ld;const int N=65540;const ld pi=acos(-1.0);int T,C,_,P,n,m,a[N],i,j,pos[N],w[6];struct comp{ ld r,i; comp(ld _r=0,ld _i=0){r=_r,i=_i;} comp operator+(const comp&x){return comp(r+x.r,i+x.i);} comp operator-(const comp&x){return comp(r-x.r,i-x.i);} comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}}f[6][N],g[N];inline void FFT(comp*a,int n,int t){ for(int i=1;i<n;i++)if(i<pos[i])swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++){ int m=1<<d,m2=m<<1; ld o=pi*2/m2*t;comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2){ comp w(1,0); for(int j=0;j<m;j++){ comp&A=a[i+j+m],&B=a[i+j],t=w*A; A=B-t;B=B+t;w=w*_w; } } } if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;}void dfs(int x,int y){ if(x==P){ int i,j,k=(P-y)&1?-1:1; for(i=1;i<=y;i++)for(j=2;j<w[i];j++)k*=j; comp t(k,0); for(j=0;j<m;j++)g[j]=f[w[1]][j]; for(i=2;i<=y;i++)for(j=0;j<m;j++)g[j]=g[j]*f[w[i]][j]; for(j=0;j<m;j++)f[0][j]=f[0][j]+g[j]*t; return; } for(int i=1;i<=y+1;i++){ w[i]++; dfs(x+1,max(i,y)); w[i]--; }}int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&_,&P); for(n=i=0;i<_;i++){ scanf("%d",&a[i]); if(a[i]>n)n=a[i]; } n*=P; for(m=1;m<=n;m<<=1); j=__builtin_ctz(m)-1; for(i=0;i<m;i++)pos[i]=pos[i>>1]>>1|((i&1)<<j); for(i=0;i<=P;i++)for(j=0;j<m;j++)f[i][j]=comp(0,0); for(i=0;i<_;i++)for(j=1;j<=P;j++)f[j][j*a[i]].r+=1; for(i=1;i<=P;i++)FFT(f[i],m,1); dfs(0,0); FFT(f[0],m,-1); for(j=i=1;i<=P;i++)j*=i; printf("Case #%d:\n",++C); for(i=1;i<m;i++){ ld ans=f[0][i].r/j; if(ans>0.5)printf("%d: %.0f\n",i,(double)ans); } puts(""); } return 0;}
BZOJ2498 : Xavier is Learning to Count
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。