題意：有$n$堆石子，每堆石子數量相同，以質因數分解給出，不停地從$1$到$n$依次拿石子，使得取完后石子個數為原來的因數（不能不取），當一堆只剩$1$個時結束，問在每堆石子結束的方案數

記石子個數為$\prod\limits_{i=1}^mp_i^{e_i}$，拿石頭就是選一些$e_i$把它們減小

令一堆石子取$x$次取完的方案數為$f_x$，取$x-1$次還未取完的方案數為$g_x$，那么$g_x=f_x$，因為對于每個取$x-1$次未取完的方案，把它取完就對應一個$x$次取完的方案，對于每個$x$次取完的方案，它的前$x-1$次操作一定不完全相同，所以兩種方案數相同

記$s=\sum e_i$，那么取$j$次取完并在$i$結束的方案數為$g_{j+1}^{i-1}f_jg_j^{n-i}=f_{j+1}^{i-1}f_j^{n-i+1}$，所以答案為$ans_i=\sum\limits_{j=1}^sf_{j+1}^{i-1}f_j^{n-i+1}$

現在我們來算$f$，直接算將$e_i$分成$x$份的方案數就是$h_x=\prod\limits_{i=1}^m\binom{e_i+x-1}{x-1}$，但$h_x\ne f_x$，因為$h_x$中可能包含那些某一次一個石子都沒取的方案，所以要容斥

取$x$次中，至少有$y$次一個石子都沒取的方案數為$\binom xyh_{x-y}$，那么$f_x=\sum\limits_{y=0}^x(-1)^y\binom xyh_{x-y}$，也就是說求出$h$后我們就可以$O(s\log s)$求$f$了

原題中$h$可以暴力求，但毒瘤代爺稍微加強了一下數據，注意到因為$\sum e_i=s$，所以不同的$e_i$最多會有$O(\sqrt s)$個，所以我們對相同的$e_i$一起處理，就可以在$O(s\sqrt s\log s)$的時間內遞推求得$h$

總時間復雜度$O(s\sqrt s\log s)$

#include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; const int mod=998244353; int mul(int a,int b){return(ll)a*b%mod;} int ad(int a,int b){return(a+b)%mod;} int de(int a,int b){return(a-b)%mod;} void inc(int&a,int b){(a+=b)%=mod;} int pow(int a,int b){int s=1;while(b){if(b&1)s=mul(s,a);a=mul(a,a);b>>=1;}return s; } int rev[1048576],N,iN; void pre(int n){int i,k=0;for(N=1,k=0;N<=n;N<<=1)k++;for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));iN=pow(N,mod-2); } void ntt(int*a,int on){int i,j,k,t,w,wn;for(i=0;i<N;i++){if(i<rev[i])swap(a[i],a[rev[i]]);}for(i=2;i<=N;i<<=1){wn=pow(3,on==1?(mod-1)/i:mod-1-(mod-1)/i);for(j=0;j<N;j+=i){w=1;for(k=0;k<i>>1;k++){t=mul(a[i/2+j+k],w);a[i/2+j+k]=de(a[j+k],t);a[j+k]=ad(a[j+k],t);w=mul(w,wn);}}}if(on==-1){for(i=0;i<N;i++)a[i]=mul(a[i],iN);} } int e[10010],inv[300010],fac[300010],rfac[300010],h[300010],f[300010],c[300010],pe[300010],pc[300010]; int C(int n,int k){return mul(fac[n],mul(rfac[k],rfac[n-k]));} int a[1048576],b[1048576]; int main(){int m,n,s,i,j,t,M;scanf("%d%d",&m,&n);s=0;for(i=1;i<=m;i++){scanf("%d%d",&t,e+i);s+=e[i];c[e[i]]++;}M=0;for(i=1;i<=s;i++){if(c[i]){M++;pe[M]=i;pc[M]=c[i];}}fac[0]=1;for(i=1;i<=s;i++)fac[i]=mul(fac[i-1],i);rfac[s]=pow(fac[s],mod-2);for(i=s;i>0;i--)rfac[i-1]=mul(rfac[i],i);inv[1]=1;for(i=2;i<=s;i++)inv[i]=-mul(mod/i,inv[mod%i]);h[1]=1;for(i=1;i<s;i++){h[i+1]=h[i];for(j=1;j<=M;j++)h[i+1]=mul(h[i+1],pow(mul(pe[j]+i,inv[i]),pc[j]));}pre(s<<1);for(i=0;i<=s;i++){a[i]=(i&1?-1:1)*rfac[i];b[i]=mul(h[i],rfac[i]);}ntt(a,1);ntt(b,1);for(i=0;i<N;i++)a[i]=mul(a[i],b[i]);ntt(a,-1);for(i=0;i<=s;i++)f[i]=mul(a[i],fac[i]);for(i=1;i<=n;i++){t=0;for(j=1;j<=s;j++)inc(t,mul(pow(f[j+1],i-1),pow(f[j],n-i+1)));inc(t,mod);printf("%d\n",t);} }

轉載于:https://www.cnblogs.com/jefflyy/p/9617190.html

總結

以上是生活随笔為你收集整理的[xsy2880]取石子游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。