題目鏈接: https://www.lydsy.com/JudgeOnline/problem.php?id=3456

著名的多項式練習題，做法也很多，終于切掉了紀念

首先求一波遞推式: 令\(F(n)\)為\(n\)個點的有標號無向連通圖的個數(shù)，則考慮補集轉(zhuǎn)化為有標號無向不連通圖的個數(shù)，然后枚舉\(1\)號點所在聯(lián)通塊的大小: \[F(n)=2^{n\choose 2}-\sum^{n-1}_{i=1} {n-1\choose i-1} F(i)2^{n-i\choose 2}\]
這樣可以做到\(O(n^2)\), 后面就該大佬們各顯神通了，我在這里整理一下四種做法:

做法一

直接使用分治NTT優(yōu)化，時間復雜度\(O(n\log^2n)\)。但我不會分治NTT，所以不具體說了。

做法二

\[F(n)=2^{n\choose 2}-\sum^{n-1}_{i=1}\frac{(n-1)!}{(i-1)!(n-i)!}F(i)2^{n-i\choose 2}\\ \frac{F(n)}{(n-1)!}=\frac{2^{n\choose 2}}{(n-1)!}-\sum^{n-1}_{i=1} \frac{F(i)}{(i-1)!}\frac{2^{n-i\choose 2}}{(n-i)!}\]移項可得\[\frac{2^{n\choose 2}}{(n-1)!}=\sum^{n}_{i=1} \frac{F(i)}{(i-1)!}\frac{2^{n-i\choose 2}}{(n-i)!}\]
令\(A(x)=\sum_{n>0}\frac{F(n)}{(n-1)!}, G(x)=\sum_{n\ge 0}\frac{2^{n\choose 2}}{n!}, H(x)=\sum_{n>0}\frac{2^{n\choose 2}}{(n-1)!}\), 則有\[F(x)G(x)=H(x)\\ F(x)=H(x)G(x)^{-1}\]
多項式求逆即可。

時間復雜度\(O(n\log n)\).

這應該是代碼復雜度和運行效率上最好的一種做法，但是做法三和做法四也有一定的啟發(fā)意義。

做法三

設(shè)\(G(n)=2^{n\choose 2}\)表示\(n\)個點有標號無向圖的個數(shù)。設(shè)\(F(x),G(x)\)分別為\(F(n),G(n)\)的指數(shù)生成函數(shù)(EGF).
由于一個有標號無向圖由若干個彼此之間無順序的聯(lián)通塊組成，因此其指數(shù)生成函數(shù)\(G(x)=\sum_{n\ge 1}\frac{F(x)^n}{n!}\).
即\(G(x)=e^{F(x)}\), \(F(x)=\ln G(x)\). 多項式\(\ln\)即可。

時間復雜度\(O(n\log n)\).

做法四

(這個做法是我自己想的，有錯敬請指出)(這種做法其實是用另一種方式推導做法三)
感謝_rqy大爺博客里的生成函數(shù)簡介。
仿照求Bell數(shù)的EGF方法，進行以下推導: \[\frac{F(n)}{n!}=\frac{G(n)}{n!}-\sum^{n-1}_{i=1} \frac{F(i)}{n(i-1)!}\frac{G(n-i)}{(n-i)!}\\ \frac{G(n)}{n!}=\frac{F(n)}{n!}+\frac{1}{n}\sum^{n-1}_{i=1}\frac{iF(i)}{i!}\frac{G(n-i)}{(n-i)!}\]
這里我們發(fā)現(xiàn)\(\frac{iF(i)}{i!}\)就是\([x^{i-1}]F'(x)\), 于是上式可以改寫為\[[x^n]G(x)=[x^n]F(x)+\frac{1}{n}\sum^{n-1}_{i=1}[x^{i-1}]F'(x)\times [x^{n-i}]G(x)\\ =\frac{1}{n}(n[x^n]F(x)+\sum^{n-1}_{i=1}[x^{i-1}]F'(x)\times [x^{n-i}]G(x))\\ =\frac{1}{n}\sum^{n}_{i=1}[x^{i-1}]F'(x)\times [x^{n-i}]G(x)\\ G(x)=\int^x_0 F'(x)G(x)\textze8trgl8bvbqx\\ \frac{G'(x)}{G(x)}=F'(x)\\ \ln G(x)=F(x)\].

一定要注意求和邊界! 我推式子的時候沒注意求和上界是\(n\)還是\((n-1)\)的問題結(jié)果一直推出來\(G(x)=F(x)+\int^x_0 F'(x)G(x)\textze8trgl8bvbqx\)查了一小時……

代碼

做法二

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #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 = 1004535809; const int G = 3; llong fact[N+3],finv[N+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) {quickpow(x,P-2);}namespace Polynomial {llong tmp1[N+3],tmp2[N+3],tmp3[N+3],tmp4[N+3],tmp5[N+3],tmp6[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;}}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);for(int j=0; j<dgr; j+=(i<<1)){llong expn = 1ll;for(int k=0; k<i; k++){llong x = ret[j+k],y = ret[i+j+k]*expn%P;ret[j+k] = (x+y)%P;ret[j+i+k] = (x-y+P)%P;expn = expn*tmp%P;}}}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++) tmp2[i] = tmp1[i]*tmp2[i]%P;ntt(dgr<<1,-1,tmp2,ret);}void polyinv(int dgr,llong poly[],llong ret[]){for(int i=0; i<dgr; i++) ret[i] = tmp1[i] = 0ll;ret[0] = mulinv(poly[0]); tmp1[0] = poly[0];for(int i=1; i<=(dgr>>1); i<<=1){for(int j=i; j<(i<<1); j++) tmp1[j] = poly[j];ntt((i<<2),1,ret,tmp2); ntt((i<<2),1,tmp1,tmp3);for(int j=0; j<(i<<2); j++) tmp2[j] = tmp2[j]*tmp2[j]%P*tmp3[j]%P;ntt((i<<2),-1,tmp2,tmp3);for(int j=0; j<(i<<1); j++) ret[j] = (2ll*ret[j]-tmp3[j]+P)%P;}} } llong f[N+3],g[N+3],h[N+3],ginv[N+3]; int n;int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;scanf("%d",&n); int dgr = Polynomial::getdgr(n);for(int i=0; i<=n; i++) {g[i] = quickpow(2ll,i*(i-1ll)/2ll)*finv[i]%P;}for(int i=1; i<=n; i++) {h[i] = quickpow(2ll,i*(i-1ll)/2ll)*finv[i-1]%P;} // printf("g: "); for(int i=0; i<dgr; i++) printf("%lld ",g[i]); puts(""); // printf("h: "); for(int i=0; i<dgr; i++) printf("%lld ",h[i]); puts("");Polynomial::polyinv(dgr,g,ginv); // printf("ginv: "); for(int i=0; i<dgr; i++) printf("%lld ",ginv[i]); puts("");Polynomial::polymul(dgr,ginv,h,f);printf("%lld\n",f[n]*fact[n-1]%P);return 0; }

生成函數(shù)這東西真的是有趣！！！

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3456 城市规划 (组合计数、DP、FFT)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。