題目

Source

http://www.tsinsen.com/A1493

Description

剛剛解決完電力網絡的問題, 阿貍又被領導的任務給難住了.
剛才說過, 阿貍的國家有n個城市, 現在國家需要在某些城市對之間建立一些貿易路線, 使得整個國家的任意兩個城市都直接或間接的連通.
為了省錢, 每兩個城市之間最多只能有一條直接的貿易路徑. 對于兩個建立路線的方案, 如果存在一個城市對, 在兩個方案中是否建立路線不一樣, 那么這兩個方案就是不同的, 否則就是相同的. 現在你需要求出一共有多少不同的方案.
好了, 這就是困擾阿貍的問題. 換句話說, 你需要求出n個點的簡單(無重邊無自環)無向連通圖數目.
由于這個數字可能非常大, 你只需要輸出方案數mod 1004535809(479 * 2 ^ 21 + 1)即可.

Input

僅一行一個整數n(<=130000)

Output

僅一行一個整數, 為方案數 mod 1004535809.

Sample Input

3
4
100000

Sample Output

4
38
829847355

?

分析

樓教主男人八題也又一題是和這題一樣，n個有標號點能構成的簡單無向連通圖數，不過這題題目數據大很多。做法如下：

• 補集轉化，設$f[n]$表示n個帶標號的點能構成的簡單圖數，而只要利用$f[n]$減去不連通的數目就是要求的答案了。其中$f[n]=2^{n(n-1)/2}$，因為完全圖有$n(n-1)/2$條邊，對于每條邊選或不選來構成一張簡單圖。

• $dp[n]$表示n個帶標號的點能構成的簡單無向連通圖數
• 考慮通過固定一個點，枚舉這個點所在連通塊的大小來轉移：$dp[n]\ =\ f[n]-\sum_{i=1}^{n-1}C_{n-1}^{i-1}dp[i]f[n-i]$
• 整理成卷積形式：$d[n]\ =\ f[n]-(n-1)!\sum_{i=1}^{n-1}((i-1)!)^{-1}d[i] \times ((n-i)!)^{-1}f[n-i]$
• 最后就是用分治FFT來做了。

?

代碼

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 262144//const long long P=50000000001507329LL; // 190734863287 * 2 ^ 18 + 1 const int P=1004535809; // 479 * 2 ^ 21 + 1 //const int P=998244353; // 119 * 2 ^ 23 + 1 const int G=3;long long mul(long long x,long long y){return x*y%P; } long long qpow(long long x,long long k){long long ret=1;while(k){if(k&1) ret=mul(ret,x);k>>=1;x=mul(x,x);}return ret; }long long wn[25]; void getwn(){for(int i=1; i<=21; ++i){int t=1<<i;wn[i]=qpow(G,(P-1)/t);} }int len; void NTT(long long y[],int op){for(int i=1,j=len>>1,k; i<len-1; ++i){if(i<j) swap(y[i],y[j]);k=len>>1;while(j>=k){j-=k;k>>=1;}if(j<k) j+=k;}int id=0;for(int h=2; h<=len; h<<=1) {++id;for(int i=0; i<len; i+=h){long long w=1;for(int j=i; j<i+(h>>1); ++j){long long u=y[j],t=mul(y[j+h/2],w);y[j]=u+t;if(y[j]>=P) y[j]-=P;y[j+h/2]=u-t+P;if(y[j+h/2]>=P) y[j+h/2]-=P;w=mul(w,wn[id]);}}}if(op==-1){for(int i=1; i<len/2; ++i) swap(y[i],y[len-i]);long long inv=qpow(len,P-2);for(int i=0; i<len; ++i) y[i]=mul(y[i],inv);} } void Convolution(long long A[],long long B[],int n){for(len=1; len<(n<<1); len<<=1);for(int i=n; i<len; ++i){A[i]=B[i]=0;}NTT(A,1); NTT(B,1);for(int i=0; i<len; ++i){A[i]=mul(A[i],B[i]);}NTT(A,-1); }long long A[MAXN],B[MAXN];long long d[MAXN],f[MAXN]={1},fact[MAXN]={1},fact_inv[MAXN]={1}; /*d[n] = f[n]-fact[n-1]*Σ(fact_inv[i-1]*d[i]*f[n-i]*fact_inv[n-i]) */ void cdq(int l,int r){if(l==r) return;int mid=l+r>>1;cdq(l,mid);for(int i=l; i<=mid; ++i){A[i-l]=mul(fact_inv[i-1],d[i]);}for(int i=mid-l+1; i<=r-l; ++i) A[i]=0;for(int i=0; i<=r-l; ++i){B[i]=mul(fact_inv[i],f[i]);}Convolution(A,B,r-l+1);for(int i=mid+1; i<=r; ++i){d[i]-=mul(fact[i-1],A[i-l]);if(d[i]<0) d[i]+=P;}cdq(mid+1,r); }int main(){getwn();for(int i=1; i<=130000; ++i){fact[i]=mul(fact[i-1],i);fact_inv[i]=qpow(fact[i],P-2);d[i]=f[i]=qpow(2,(i-1LL)*i/2);}cdq(1,130000);int n;while(~scanf("%d",&n)){printf("%lld\n",d[n]);}return 0; }

?

轉載于:https://www.cnblogs.com/WABoss/p/5929692.html

總結

以上是生活随笔為你收集整理的Tsinsen A1493 城市规划（DP + CDQ分治 + NTT）的全部內容，希望文章能夠幫你解決所遇到的問題。

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