题目链接：Luogu 4841

阿狸的国家有 $n$ 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。

为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。

换句话说，你需要求出 $n$ 个点的简单（无重边无自环）无向连通图数目。由于这个数字可能非常大，你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。

数据范围：$1 \le n \le 1.3 \times 10 ^ 5$。

Solution

有标号无向连通图计数。

设 $f_i$ 表示 $i$ 个点的无向连通图数量，$g_i$ 表示 $i$ 个点的无向图数量。那么我们考虑 $f_i, g_i$ 的指数型生成函数：

$$ F(x) = \sum_{i = 0} ^ {\infty} \frac{f_i x^i}{i!} $$

我们枚举连通块数量 $k$ 得到：

$$ G(x) = \sum_{k = 0} ^ {\infty} \frac{F ^ k (x)}{k!} $$

即：

$$ G = e ^ F \\ F = \ln G $$

显然有：

$$ g_i = \frac{2 ^ {\binom{i}{2}}}{i!} $$

直接上多项式板子！

时间复杂度：$\mathcal O(n \log n)$。

Code

/* 此处省略多项式模板 */

int main() {
    int n;
    scanf("%d", &n);
    Vec A(n + 1);
    A[0] = 1;
    int fac = 1, c = 0;
    for (int i = 1; i <= n; i++) {
        fac = 1LL * fac * i % MOD;
        A[i] = 1LL * pow(2, c) * inv(fac) % MOD;
        c = (c + i) % (MOD - 1);
    }
    printf("%d\n", 1LL * ln(A)[n] * fac % MOD);
    return 0;
}