难度：NOI/NOI+/CTSC

题目描述

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

输入格式

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

输出格式

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

题解

        题目很清晰，就是求$n$个点的连通图数量，每一个点都是互不同的（点的编号顺序不同也算一种方案）。
        设$f(x)$是$x$个点的连通图数量，$g(x)$是$x$个点随便连的数量，那么显然有：

        考虑结点1所在的连通块大小，进行枚举，就可以得到：

        这是本题很巧妙的一步，然后得到：

        就是：

        设$F(x)=\frac {f(x)} {(x-1)!}$且$G(x)=\frac {g(x)} {x!},H(x)=\frac{g(x)}{(x-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
#include <bits/stdc++.h>

#define MOD 1004535809
#define G 3
#define N 130005
using namespace std;
int tr[N << 2];
struct Pol {
    int l, op[N << 2] = {0};
} pol1, pol2, tmp, pol3;
int n, fac[N], bin[N], iv[N];

int qPow(int a, long long b) {
    int ans = 1, x = a;
    while (b) {
        if (b & 1)ans = 1ll * ans * x % MOD;
        x = 1ll * x * x % MOD, b >>= 1;
    }
    return ans;
}

void NTT(int l, int *c, int type) {
    for (int i = 0; i < l; i++)if (i < tr[i])swap(c[i], c[tr[i]]);
    for (int mid = 1; mid < l; mid <<= 1) {
        int wn = qPow(G, (MOD - 1) / (mid << 1));
        if (type == -1)wn = qPow(wn, MOD - 2);
        for (int len = mid << 1, j = 0; j < l; j += len) {
            int w = 1;
            for (int k = 0; k < mid; k++, w = 1ll * w * wn % MOD) {
                int x = c[j + k], y = 1ll * w * c[j + mid + k] % MOD;
                c[j + k] = (1ll * x + y) % MOD, c[j + mid + k] = (1ll * x - y) % MOD;
            }
        }
    }
}

void inv(Pol *ans, const Pol *x, int rk) {
    if (rk == 1) {
        ans->l = 0, ans->op[0] = qPow(x->op[0], MOD - 2);
        return;
    }
    inv(ans, x, (rk + 1) >> 1);
    int l = 1, le = 0;
    while (l <= (rk << 1))l <<= 1, ++le;
    for (int i = 0; i < l; i++) {
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (le - 1));
        tmp.op[i] = i <= min(x->l, rk - 1) ? x->op[i] : 0;
        ans->op[i] = i <= ans->l ? ans->op[i] : 0;
    }
    NTT(l, tmp.op, 1), NTT(l, ans->op, 1);
    for (int i = 0; i < l; i++)
        ans->op[i] = (2ll * ans->op[i] % MOD - (1ll * tmp.op[i] * ans->op[i] % MOD) * 1ll * ans->op[i] % MOD) % MOD;
    NTT(l, ans->op, -1), l = qPow(l, MOD - 2), ans->l = rk - 1;
    for (int i = 0; i <= ans->l; i++)ans->op[i] = 1ll * ans->op[i] * l % MOD;
}

inline void multiple(Pol *ans, Pol *a, Pol *b) {=
    int l = 1, le = 0;
    while (l <= a->l + b->l)l <<= 1, ++le;
    for (int i = 0; i < l; i++) {
        tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (le - 1));
        if (i > a->l)a->op[i] = 0;=
        if (i > b->l)b->op[i] = 0;
    }
    NTT(l, a->op, 1), NTT(l, b->op, 1);
    for (int i = 0; i < l; i++)a->op[i] = 1ll * a->op[i] * b->op[i] % MOD;
    NTT(l, a->op, -1), l = qPow(l, MOD - 2), ans->l = a->l + b->l;
    for (int i = 0; i <= ans->l; i++)ans->op[i] = 1ll * a->op[i] * l % MOD;
}

int main() {
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; i++)fac[i] = 1ll * i * fac[i - 1] % MOD;
    for (int i = 0; i <= n; i++)iv[i] = qPow(fac[i], MOD - 2);
    for (int i = 0; i <= n; i++)bin[i] = qPow(2, 1ll * i * (i - 1) / 2);
    for (int i = 0; i <= n; i++)pol1.op[i] = 1ll * bin[i] * iv[i] % MOD;
    for (int i = 1; i <= n; i++)pol2.op[i] = 1ll * bin[i] * iv[i - 1] % MOD;
    pol1.l = pol2.l = n;
    inv(&pol3, &pol1, n), multiple(&pol1, &pol2, &pol3);
    printf("%d", (1ll * pol1.op[n] + MOD) % MOD * fac[n - 1] % MOD);
    return 0;
}