BZOJ2629 : binomial

2019-04-14 17:36发布

站内文章 / 模拟电子
12865 0 1415
根据Lucas定理，等价于在$P$进制下每一位分别求组合数最后乘积模$P$。 因为答案为$0$的并不好算，所以可以考虑用$n+1$减去其它所有的答案。 那么每一位的组合数都不能是$0$，那么这就保证了$k$的每一位都不大于$n$，所以无需考虑$kleq n$这个限制。 求出模$P$下每个数的指标，考虑数位DP，设$f[i][j]$表示考虑了最后$i$位，组合数的指标之和模$varphi(P)$为$j$的方案数。 那么转移就是卷积的形式，FFT加速即可。 时间复杂度$O(Plog Plog n)$。   #include #include #include #include using namespace std; const int P=51061,F=P-1,O=29,N=131100; const double pi=acos(-1.0); char s[P]; int flag,n=131072,len,i,j,po[P],ind[P],fac[P],inv[P],a[P],ans[P],pos[N],f[N],g[N]; struct comp{ double r,i;comp(double _r=0,double _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);} comp conj(){return comp(r,-i);} }A[N],B[N]; inline int C(int n,int m){return 1LL*fac[n]*inv[m]*inv[n-m]%P;} void FFT(comp*a,int t){ for(int i=1;i>1]>>1|((i&1)< 　　

热门文章