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

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

题解

题意

求$n$个点的简单(无重边无自环)有标号无向连通图数目，对$1004535809$取模。

解法

设$f(n)$为点数为$n$的无向连通图的数量，$g(n)$为点数为$n$的无向图之间连边的方案数，对于任意两个点可以连或不连，易得$g(n) = 2 ^ {\binom{n}{2}}$，然后钦定一个点， 枚举设这个点的连通块大小，得

$$g(n) = \sum_{i = 1} ^ n \dbinom{n - 1}{i - 1}f(i) g(n - i)$$

然后化简式子

$$2^{\binom{n}{2}} = \sum_{ i= 1}^n \dbinom{n - 1}{i - 1}f(i)2^{\binom{n - i}{2}}\\ \frac{2 ^ {\binom{n}{2}}}{(n - 1) !} = \sum_{i = 1} ^ n \frac{f(i)}{(i - 1) !} \frac{2 ^ {\binom{n - i}{2}}}{(n - i)!}$$

可以看出是一个卷积的形式，然后构造多项式

$$F(x) = \sum_{i = 1} ^ {\infty} \frac{f(i)}{(i - 1) !}x^i \\ G(x) = \sum_{i = 0} ^ {\infty}\frac{2 ^ {\binom{i}{2}}}{i!}x^i \\ H(x) = \sum_{i = 1} ^ {\infty} \frac{2 ^ {\binom{i}{2}}}{(i - 1) !}x^i$$

之前推出来$H = F \ast G$， 所以$F = H \ast G ^{-1} \pmod {x ^ {n + 1}}$

#include <bits/stdc++.h>

using namespace std;

namespace Poly// 使用NTT实现
{
    #define int long long
    #define vec vector <int>
    const int mod = 1004535809; // 模数
    const int g = 3; // 原根
    const int gi = 334845270; // 逆元
    const int N = 6e5 + 10; // size

    int recover[N];
    
    int qpow(int a, int b)
    {
        int t = 1;
        while(b != 0)
        {
            if(b & 1)t = t * a % mod;
            a = a * a % mod; b >>= 1;
        }
        return t;
    }// 快速幂
    
    int inv(int x) { return qpow(x, mod - 2);}// 逆元
    
    void init(int n, int m, int &len)
    {
        len = 1; int cnt = 0;
        while(len <= (n + m))len <<= 1, cnt ++;
        for(int i = 0; i < len; i++)
            recover[i] = (recover[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
    }// 初始化
    
    void NTT(vec &a, int len, int type)
    {
        for(int i = 0; i < len; i++)
            if(i < recover[i])swap(a[i], a[recover[i]]);
        for(int k = 1; k < len; k <<= 1)
        {
            int x = qpow(type == 1 ? g : gi, (mod - 1) / (k << 1));
            for(int i = 0; i < len; i += (k << 1))
            {
                int w = 1;
                for(int j = 0; j < k; j++)
                {
                    int y = a[i + j] % mod;
                    int z = w * a[i + j + k] % mod;
                    a[i + j] = (y + z) % mod;
                    a[i + j + k] = ((y - z) % mod + mod) % mod;
                    w = w * x % mod;
                }
            }
        }
        if(type == -1)
        {
            int iv = inv(len);
            for(int i = 0; i < len; i++)
                a[i] = a[i] * iv % mod;
        }
    }// NTT
    
    struct poly
    {
        vector <int> v; int len;
        poly(){v.resize(N); len = 0;}
        void clear(int n){v.clear(); v.resize(N); len = n;}
        void length(int n){len = n;}
        void memset0(int l, int r){for(int i = l; i < r; i++)v[i] = 0;}
        void print(int n){for(int i = 0; i < n; i++)printf("%lld ", v[i]); printf("\n");}
    
        friend poly operator + (poly A, poly B)
        {
            A.length(max(A.len, B.len));
            for(int i = 0; i <= A.len; i++)
                A.v[i] = (A.v[i] + B.v[i]) % mod;
            return A;
        }
    
        friend poly operator - (poly A, poly B)
        {
            A.length(max(A.len, B.len));
            for(int i = 0; i <= A.len; i++)
                A.v[i] = ((A.v[i] - B.v[i]) % mod + mod) % mod;
            return A;
        }
    
        friend poly operator * (poly A, poly B)
        {
            int len; init(A.len, B.len, len);
            NTT(A.v, len, 1), NTT(B.v, len, 1);
            for(int i = 0; i < len; i++)
                A.v[i] = (A.v[i] * B.v[i]) % mod;
            NTT(A.v, len, -1); A.len += B.len;
            return A;
        }
    };
    
    vec tmp;
    
    void inverse(poly &A, poly &B, int n)
    {
        if(n == 1){B.v[0] = inv(A.v[0]);return;}
        inverse(A, B, (n + 1) >> 1);
        int len; init(n, n, len);
        tmp.clear(); tmp.resize(len);
        for(int i = 0; i < n; i++) tmp[i] = A.v[i];
        NTT(tmp, len, 1), NTT(B.v, len, 1);
        for(int i = 0; i < len; i++)
            B.v[i] = (2 - B.v[i] * tmp[i] % mod + mod) % mod * B.v[i] % mod;
        NTT(B.v, len, -1);
        for(int i = n; i < len; i++)B.v[i] = 0;
    }// 乘法逆
    
    void diff(poly &A, poly &B, int n)
    {
        for(int i = 1; i < n; i++)
            B.v[i - 1] = i * A.v[i] % mod;
        B.v[n - 1] = 0; B.length(n);
    }// 多项式求导
    
    void integ(poly &A, poly &B, int n)
    {
        for(int i = 1; i < n; i++)
            B.v[i] = A.v[i - 1] * inv(i) % mod;
        B.v[0] = 0; B.length(n);
    }// 多项式积分
    
    poly C, D, E, F, G, H, I;
    
    void Ln(poly &A, poly &B, int n)
    {
        E.clear(n); F.clear(n);
        diff(A, E, n); inverse(A, F, n);
        E = E * F;
        integ(E, B, n); B.length(n);
    }// 多项式ln函数
    
    void Exp(poly &A, poly &B, int n)
    {
        if(n == 1){B.v[0] = 1; return;}
        Exp(A, B, (n + 1) >> 1);
        int len; init(n, n, len);
        C.clear(n); D.clear(n); C.v[0] = 1;
        Ln(B, D, n); C = B * (C + A - D);
        for(int i = 0; i < n; i++)B.v[i] = C.v[i];
        for(int i = n; i < len; i++)B.v[i] = 0;
    }// 多项式exp函数
    
    const int inv2 = inv(2);
    
    void Sqrt(poly &A, poly &B, int n)
    {
        if(n == 1){B.v[0] = 1; return;}
        Sqrt(A, B, (n + 1) >> 1);
        int len; init(n, n, len);
        G.clear(n); H.clear(n); inverse(B, H, n);
        for(int i = 0; i < n; i++)G.v[i] = A.v[i];
        NTT(H.v, len, 1), NTT(B.v, len, 1), NTT(G.v, len, 1);
        for(int i = 0; i < len; i++)
            B.v[i] = (B.v[i] + G.v[i] * H.v[i] % mod) % mod * inv2 % mod;
        NTT(B.v, len, -1);
        for(int i = n; i < len; i++)B.v[i] = 0;
    }// 多项式开根
    
    void Pow(poly &A, poly &B, int n, int k)
    {
        I.clear(n); Ln(A, I, n);
        for(int i = 0; i < n; i++)(I.v[i] *= k) %= mod;
        Exp(I, B, n);
    }// 多项式幂函数
    
    #undef int

}

using namespace Poly;

#define int long long

int n;

int fac[N], ifac[N];

int c(int n, int m)
{
    if(n < m)return 0;
    return n * (n - 1) / 2 % (mod - 1);
}

signed main()
{
    scanf("%lld", &n);
    n = n + 1;
    fac[0] = ifac[0] = 1;
    for(int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    for(int i = 1; i <= n; i++)
        ifac[i] = inv(fac[i]);
    poly F, G, H;
    G.clear(n);
    for(int i = 0; i < n; i++)
        G.v[i] = qpow(2, c(i, 2)) * ifac[i] % mod;
    H.clear(n);
    for(int i = 1; i < n; i++)
        H.v[i] = qpow(2, c(i, 2)) * ifac[i - 1] % mod;
    F.clear(n);
    inverse(G, F, n);
    F = F * H;
    printf("%lld", F.v[n - 1] * fac[n - 2] % mod);
    return 0;
}