luogu P4841 [集训队作业2013]城市规划 FFT

FFT神仙题，强烈建议先自己推一推式子再看题解。

首先正着想比较难想，正难则反，所以我们先考虑一下全集。设\(\displaystyle g[n]=2^{C_n^2}\)(C为组合数),表示n个有标号的点随便连边的方案数，设\(f[n]\)是n个有标号的点的无向连通图的方案数。

考虑\(g\)和\(f\)之间的关系，因为每一个点都不一样，所以我们枚举1号点所在连通图的大小就可以得到

\(\displaystyle f[n]=g[n]-\sum_{i=1}^{n-1}C_{n-1}^{i-1}f[i]g[n-i]\),

后面的\(\sum_{i=1}^{n-1}C_{n-1}^{i-1}f[i]g[n-i]\)是枚举1号点所在联通块的大小，注意这里i不能等于n，因为等于n的时候它是一个连通图。

我们将等号两边转移一下得到

\(\displaystyle g[n]=\sum_{i=1}^{n-1}C_{n-1}^{i-1}f[i]g[n-i]+f[n]\)

因为\(i=n\)时，\(C_{n-1}^{n-1}f[n]g[0]=f[n]\),所以

\(\displaystyle g[n]=\sum_{i=1}^{n}C_{n-1}^{i-1}f[i]g[n-i]\)

我们知道\(\displaystyle C_n^m=\frac{n!}{m!(n-m)!}\),所以

\(\displaystyle g[n]=\sum_{i=1}^{n}(n-1)!\frac{f[i]}{(i-1)!}\frac{g[n-i]}{(n-i)!}\)

因为\((n-1)!\)和\(i\)无关。所以

\(\displaystyle g[n]=(n-1)!\sum_{i=1}^{n}\frac{f[i]}{(i-1)!}\frac{g[n-i]}{(n-i)!}\)

\(\displaystyle \frac{g[n]}{(n-1)!}=\sum_{i=1}^{n}\frac{f[i]}{(i-1)!}\frac{g[n-i]}{(n-i)!}\)

我们设\(\displaystyle H[n]=\frac{g[n]}{(n-1)!}\) \(\displaystyle F[n]=\frac{f[n]}{(n-1)!}\) \(\displaystyle G[n]=\frac{g[n]}{n!}\)

就能得到

\(\displaystyle H[n]=\sum_{i=1}^nF[i]G[n-i]\)

又因为\(i=0\)时\(F[i]=0\).所以

\(\displaystyle H[n]=\sum_{i=0}^nF[i]G[n-i]\)

\(\displaystyle H=F*G\)

\(\displaystyle F=\frac{H}{G}\)

\(\displaystyle F=HG^{-1}\)

因为 \(H\)和\(G\)已知的，所以我们多项式求个逆就OK啦。

时间复杂度\(O(nlogn)\)。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
const int N = 500010, mod = 1004535809, YY = 3, YYinv = (mod + 1) / 3;
int r[N];
LL c[N], jc[N], inv[N], F[N], G[N], Ginv[N], H[N];
int read() 
{
    int x = 0; int f = 0; char c = getchar();
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
LL ksm(LL a, LL b, LL mod) 
{
    LL res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)res = res * a % mod;
    return res;
}
void NTT(LL *A, int lim, int opt) 
{
    for (int i = 0; i < lim; ++i)r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
    for (int i = 0; i < lim; ++i)
        if (i < r[i])swap(A[i], A[r[i]]);
    int len;
    LL wn, w, x, y;
    for (int mid = 1; mid < lim; mid <<= 1) 
    {
        len = mid << 1;
        wn = ksm(opt == 1 ? YY : YYinv, (mod - 1) / len, mod);
        for (int j = 0; j < lim; j += len) 
        {
            w = 1;
            for (int k = j; k < j + mid; ++k, w = w * wn % mod) 
            {
                x = A[k]; y = A[k + mid] * w % mod;
                A[k] = (x + y) % mod;
                A[k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if (opt == 1)return;
    LL ni = ksm(lim, mod - 2, mod);
    for (int i = 0; i < lim; ++i)A[i] = A[i] * ni % mod;
}
void MUL(LL*A, int n, LL *B, int m) 
{
    int lim = 1;
    while (lim <= (n + m))lim <<= 1;
    NTT(A, lim, 1); NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i)A[i] = A[i] * B[i] % mod;
    NTT(A, lim, -1);
}
void INV(int siz, LL *A, LL *B) 
{
    if (siz == 1) 
    {
        B[0] = ksm(A[0], mod - 2, mod);
        return;
    }
    INV((siz + 1) >> 1, A, B);
    int lim = 1;
    while (lim < (siz << 1))lim <<= 1;
    for (int i = 0; i < siz; ++i)c[i] = A[i];
    for (int i = siz; i < lim; ++i)c[i] = 0;
    NTT(c, lim, 1); NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i)B[i] = B[i] * (2 - c[i] * B[i] % mod + mod) % mod;
    NTT(B, lim, -1);
    for (int i = siz; i < lim; ++i)B[i] = 0;
}
void YYCH() 
{
    jc[0] = jc[1] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; ++i)jc[i] = jc[i - 1] * i % mod;
    inv[n] = ksm(jc[n], mod - 2, mod);
    for (int i = n - 1; i >= 1; --i)inv[i] = inv[i + 1] * (i + 1) % mod;

    for (int i = 0; i <= n; ++i)G[i] = ksm(2, (LL)i * (i - 1) / 2, mod) * inv[i] % mod;
    for (int i = 1; i <= n; ++i)H[i] = ksm(2, (LL)i * (i - 1) / 2, mod) * inv[i - 1] % mod;
}
signed main() 
{
    cin >> n;
    YYCH();
    INV(n + 1, G, Ginv);
    MUL(H, n, Ginv, n);
    cout << H[n]*jc[n - 1] % mod;
    return 0;
}