BZOJ 3456 城市規劃：FFT 快速傅里葉變換計算連通圖計數

問題描述

求 n (≤ 130,000) 個標號點的無向簡單連通圖個數，模 P = 1004535809（= 479×2²¹+1，適合 NTT）。

組合數學推導

設 fᵢ = i 個點的連通圖數。總圖數（不要求連通）= 2^{C(i,2)}。
考慮包含點 1 的連通塊大小為 j (1 ≤ j ≤ i)：
選 j-1 個點陪伴點 1：C(i-1, j-1)
這 j 個點形成連通圖：fⱼ
剩餘 i-j 個點任意連邊：2^{C(i-j,2)}
遞推：

2^{C(i,2)} = Σ_{j=1..i} C(i-1, j-1) * fⱼ * 2^{C(i-j,2)}

移項得 fᵢ 遞推，但直接算 O(n²) 太慢。

生成函數 + 多項式求逆 + NTT

定義指數生成函數（EGF）：

A(x) = Σ fᵢ/(i-1)! xⁱ
B(x) = Σ 2^{C(i,2)}/i! xⁱ
C(x) = Σ 2^{C(i,2)}/(i-1)! xⁱ

遞推式對應卷積：A(x) * B(x) = C(x)。
故 A(x) = C(x) * B(x)⁻¹。
需計算多項式 B(x) 的逆（模 x^{n+1}），再與 C(x) 卷積。均用 NTT（數論變換，模數為質數且原根存在）。

NTT 關鍵參數

• 模數 P = 1004535809 = 479×2²¹+1，原根 G = 3。
• 最大長度 2²¹ > 2×130,000，足夠。
• 預計算階乘、逆元、2 的冪次模 P-1（指數模 P-1）。

代碼框架（核心部分）

const int MOD = 1004535809, G = 3;
int modPow(int a, ll e) { int r=1; for(;e;e>>=1,a=1ll*a*a%MOD) if(e&1) r=1ll*r*a%MOD; return r; }
void NTT(vector& a, bool inv) { /* 標準迭代NTT */ }
vector polyInv(const vector& a, int n) { /* 牛頓疊代求逆 */ }
int main() {
    int n; cin >> n;
    int m = 1; while (m <= n) m <<= 1; m <<= 1; // 卷積長度
    vector B(m), C(m), fac(n+1), ifac(n+1);
    fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD;
    ifac[n]=modPow(fac[n], MOD-2); for(int i=n;i>0;i--) ifac[i-1]=1ll*ifac[i]*i%MOD;
    for(int i=0;i<=n;i++) {
        int e = 1ll*i*(i-1)/2 % (MOD-1);
        int p2 = modPow(2, e);
        B[i] = 1ll * p2 * ifac[i] % MOD;
        if (i) C[i] = 1ll * p2 * ifac[i-1] % MOD;
    }
    auto invB = polyInv(B, m);
    NTT(invB, false); NTT(C, false);
    for(int i=0;i