題意:

題解: 這道題我思路大方向是正確的，但是生成函數推錯導致一直WA，看了標程才改對……

首先一個長為\(m\)的輪換的\(n\)次冪會分裂成\(\gcd(n,m)\)個長為\(\frac{m}{\gcd(n,m)}\)的輪換
所以合并的時候相當于對于一個長度\(l\)若存在一個\(m\)使得\(\frac{m}{\gcd(n,m)}=l\)則\(\gcd(n,m)\)個長度為\(l\)的輪換可以合并

顯然不同長度的輪換是互不影響的，那么我們可以分開每種長度計算
就相當于對于一個長度為\(l\)的有標號的輪換，要把它們劃分成若干無標號集合，每個集合大小都在給定的集合\(S\)內，并且每個集合有權值(合并的方案數)，一種劃分方案的權值為所有集合權值之積，求所有劃分方案權值總和
那么顯然這個東西的EGF就等于\(\exp(\sum_{i\in S} \frac{w_i}{i!})\), \(w_i\)為權值

如何求\(w_i\)? 在這里我出了問題
正確的答案是，假設\(k\)個長度為\(l\)的輪換合并，方案數為\(l^{k-1}(k-1)!\), 也就是\(\frac{l^kk!}{lk}\).
這大概是因為，假設我們定住第一個輪換的第一個元素的位置，那么其余每個輪換自身內部的順序都可以改變，這樣是\(l^{k-1}\)種；這些輪換之間的順序也可以改變，這樣是\((k-1)!\)種。

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<vector> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 1<<19; const int LGN = 19; const int P = 998244353; const int G = 3;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong mulinv(llong x) {return quickpow(x,P-2);}namespace FFT {llong tmp1[N+3],tmp2[N+3],tmp3[N+3],tmp4[N+3],tmp5[N+3],tmp6[N+3],tmp7[N+3],tmp8[N+3],tmp9[N+3],tmp10[N+3];llong tst1[N+3],tst2[N+3],tst3[N+3];llong sexp[N+3];int fftid[N+3];int getdgr(int n) {int ret = 1; while(ret<=n) ret<<=1; return ret;}void init_fftid(int dgr){int len = 0; for(int i=1; i<=LGN; i++) {if((1<<i)==dgr) {len = i; break;}}fftid[0] = 0; for(int i=1; i<dgr; i++) fftid[i] = (fftid[i>>1]>>1)|((i&1)<<(len-1));}void ntt(int dgr,int coe,llong poly[],llong ret[]){init_fftid(dgr);if(poly==ret) {for(int i=0; i<dgr; i++) {if(i<fftid[i]) swap(ret[i],ret[fftid[i]]);}}else {for(int i=0; i<dgr; i++) ret[i] = poly[fftid[i]];}for(int i=1; i<=(dgr>>1); i<<=1){llong tmp = quickpow(G,(P-1)/(i<<1));if(coe==-1) {tmp = mulinv(tmp);}sexp[0] = 1ll; for(int j=1; j<i; j++) sexp[j] = sexp[j-1]*tmp%P;for(int j=0; j<dgr; j+=(i<<1)){for(llong *k=ret+j,*kk=sexp; k<ret+i+j; k++,kk++){llong y = k[i]*(*kk)%P;k[i] = (*k)-y<0 ? (*k)-y+P : (*k)-y;(*k) = (*k)+y>=P ? (*k)+y-P : (*k)+y;}}}if(coe==-1){llong tmp = mulinv(dgr);for(int i=0; i<dgr; i++) ret[i] = ret[i]*tmp%P;}}void polymul(int dgr,llong poly1[],llong poly2[],llong ret[]){ntt((dgr<<1),1,poly1,tmp1); ntt((dgr<<1),1,poly2,tmp2);for(int i=0; i<(dgr<<1); i++) ret[i] = tmp1[i]*tmp2[i]%P;ntt((dgr<<1),-1,ret,ret);}void polyinv(int dgr,llong poly[],llong ret[]){for(int i=0; i<(dgr<<1); i++) ret[i] = tmp3[i] = tmp4[i] = tmp5[i] = 0ll;ret[0] = mulinv(poly[0]);for(int i=1; i<=(dgr>>1); i<<=1){for(int j=0; j<(i<<1); j++) tmp3[j] = poly[j];ntt((i<<2),1,tmp3,tmp4); ntt((i<<2),1,ret,tmp5);for(int j=0; j<(i<<2); j++) tmp3[j] = tmp4[j]*tmp5[j]%P*tmp5[j]%P;ntt((i<<2),-1,tmp3,tmp4);for(int j=0; j<(i<<1); j++) ret[j] = (ret[j]+ret[j]-tmp4[j]+P)%P;}}void polyder(int dgr,llong poly[],llong ret[]){for(int i=0; i<dgr-1; i++) ret[i] = poly[i+1]*(i+1)%P;ret[dgr-1] = 0ll;}void polyint(int dgr,llong poly[],llong ret[]){for(int i=1; i<dgr; i++) ret[i] = poly[i-1]*mulinv(i)%P;ret[0] = 0ll;}void polyln(int dgr,llong poly[],llong ret[]){for(int i=0; i<(dgr<<1); i++) ret[i] = tmp6[i] = tmp7[i] = tmp8[i] = 0ll;polyder(dgr,poly,tmp6);polyinv(dgr,poly,tmp7);polymul(dgr,tmp6,tmp7,tmp8);polyint(dgr,tmp8,ret);}void polyexp(int dgr,llong poly[],llong ret[]){for(int i=0; i<(dgr<<1); i++) ret[i] = tmp9[i] = tmp10[i] = 0ll;ret[0] = 1ll;for(int i=1; i<=(dgr>>1); i<<=1){polyln((i<<1),ret,tmp9);for(int j=0; j<(i<<1); j++) tmp9[j] = (-tmp9[j]+poly[j]+P)%P; tmp9[0]++;polymul((i<<2),ret,tmp9,tmp10);for(int j=0; j<(i<<1); j++) ret[j] = tmp10[j];}} } int permu[N+3]; int a[N+3]; int dgr[N+3]; bool vis[N+3]; vector<int> s[N+3]; llong f[N+3],expf[N+3]; llong fact[N+3]; int n;int gcd(int x,int y) {return y==0?x:gcd(y,x%y);}int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d",&permu[i]);for(int i=1; i<=n; i++){if(vis[i]) continue;int len = 1; vis[i] = true;for(int j=permu[i]; j!=i; j=permu[j]){len++;vis[j] = true;}a[len]++;}for(int i=1; i<=n; i++){int g = gcd(i,n),l = i/gcd(i,n);s[l].push_back(g);}llong ans = 1ll;for(int i=1; i<=n; i++){if(a[i]==0) continue;int dgr = FFT::getdgr(a[i]);for(int j=0; j<s[i].size(); j++){if(s[i][j]<dgr){f[s[i][j]] = (f[s[i][j]]+mulinv(s[i][j])*quickpow(i,s[i][j]-1))%P;}}FFT::polyexp(dgr,f,expf);ans = ans*expf[a[i]]%P*fact[a[i]]%P;for(int j=0; j<(dgr<<1); j++) f[j] = expf[j] = 0ll;}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Luogu P4709 信息传递 (群论、生成函数、多项式指数函数)的全部內容，希望文章能夠幫你解決所遇到的問題。

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