NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  • 题解
  • Description

    刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.
    刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.
    好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目.
    由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.

    Input

    仅一行一个整数n(<=130000)

    Output

    仅一行一个整数, 为方案数 mod 1004535809.

    Sample Input

    1
    3

    Sample Output

    1
    4

    HINT

    对于 100%的数据, n <= 130000

    题解

    设无向图的生成函数为$G(x)$, 无向联通图的生成函数为$f(x)$
    $$g(x) = 2^{C_n^2}$$
    枚举无向图是由几个联通图构成的:
    $$g(n) = \sum_{i = 1}^{n} { {n - 1} \choose {i - 1} } f(i) G(n - i)$$
    $$2^{n \choose 2} = \sum_{i = 1}^{n} { {n - 1} \choose {i - 1} } f(i) 2^{ {n - i} \choose 2}$$
    然后两边同时除以 $$(n-1)!$$
    $$\frac{2^{n \choose 2} }{(n-1)!} = \sum_{i = 1}^{n} \frac{f(i)}{(i-1)!} \frac{2^{ {n - i} \choose 2} }{(n-i)!}$$

    定义函数 $F(x),G(x),C(x)$

    $$F(x) = \sum_{n=1}^{\infty} \frac{f(n)}{(n-1)!}x^n$$
    $$G(x) = \sum_{n=0}^{\infty} \frac{2^{n \choose 2} }{n!}x^n $$
    $$C(x) = \sum_{n=0}^{\infty} \frac{2^{n \choose 2} }{(n-1)!}x^n$$

    $$C(x) = F(x)G(x)$$

    $$C(x) \equiv F(x)G(x) mod { x^{n+1} }$$

    $$F(x) \equiv C(x)G^{-1}(x) mod { x^{n+1} }$$

    多项式求逆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    const int MOD = 1004535809;
    const int MAXN = 1 << 18 + 1;
    long long pow_mod(long long a, int b)
    {
    long long ans = 1;
    while (b)
    {
    if (b & 1) ans = ans * a % MOD;
    b >>= 1;
    a = a * a % MOD;
    }
    return ans;
    }
    long long Inv;
    int N;
    int rev[MAXN];
    void FFt(long long *a, int op)
    {
    long long w, wn, t;
    for (int i = 1; i < N; i++)
    if (i < rev[i])
    swap(a[i], a[rev[i]]);
    for (int k = 2; k <= N; k <<= 1)
    {
    wn = pow_mod(3, op == 1 ? (MOD - 1) / k : MOD - 1 - (MOD - 1) / k);
    for (int j = 0; j < N; j += k)
    {
    w = 1;
    for (int i = 0; i < (k >> 1); i++, w = w * wn % MOD)
    {
    t = a[i + j + (k >> 1)] * w % MOD;
    a[i + j + (k >> 1)] = (a[i + j] - t + MOD) % MOD;
    a[i + j] = (a[i + j] + t) % MOD;
    }
    }
    }
    if (op == -1)
    for (int i = 0; i < N; i++)
    a[i] = a[i] * Inv % MOD;
    }
    long long tmp[MAXN];
    void Get_Inv(int dep, long long *a, long long *b)
    {
    if (dep == 1)
    return b[0] = pow_mod(a[0], MOD - 2), void();
    Get_Inv((dep + 1) >> 1, a, b);
    N = 1;
    while (N < (dep << 1))
    N <<= 1;
    Inv = pow_mod(N, MOD - 2);
    for (int i = 1; i < N; i++)
    if (i & 1)
    rev[i] = (rev[i >> 1] >> 1) | (N >> 1);
    else
    rev[i] = (rev[i >> 1] >> 1);
    copy(a, a + dep, tmp);
    fill(tmp + dep, tmp + N, 0);
    FFt(tmp, 1);
    FFt(b, 1);
    for (int i = 0; i < N; i++)
    b[i] = b[i] * ((2 - b[i] * tmp[i] % MOD + MOD) % MOD) % MOD;
    FFt(b, -1);
    fill(b + dep, b + N, 0);
    }
    long long F_Inv[MAXN];
    long long F[MAXN];
    long long C[MAXN], G[MAXN], G_Inv[MAXN];
    int main()
    {
    int n = read();
    F[0] = 1;
    for (int i = 1; i <= n; i++)
    F[i] = F[i - 1] * i % MOD;
    F_Inv[n] = pow_mod(F[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) F_Inv[i] = F_Inv[i + 1] * (i + 1) % MOD;
    for (int i = 0; i <= n; i++)
    G[i] = (i < 2) ? (1) : pow_mod(2, 1ll * i * (i - 1) / 2 % (MOD - 1)) * F_Inv[i] % MOD;
    for (int i = 0; i <= n; i++) C[i] = i * G[i] % MOD;
    Get_Inv(n + 1, G, G_Inv);
    N = 1;
    while (N <= n << 1)
    N <<= 1;
    Inv = pow_mod(N, MOD - 2);
    for (int i = 1; i < N; i++)
    if (i & 1)
    rev[i] = (rev[i >> 1] >> 1) | (N >> 1);
    else
    rev[i] = (rev[i >> 1] >> 1);
    FFt(G_Inv, 1), FFt(C, 1);
    for (int i = 0; i < N; i++) C[i] = C[i] * G_Inv[i] % MOD;
    FFt(C, -1);
    printf ("%d\n", C[n] * F[n - 1] % MOD);
    // while (1);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2018/02/26/129/

    本文最后更新于 天前,文中所描述的信息可能已发生改变