光之大陆问题

解题思路

给我们 $n$ 个点的无向完全图，然后要我们每次从中选取一些边，使得整张图连通，且只包含简单环，问我们有多少种合法的选取方案。

可以将方案拆分然后用乘法原理来解。

我们先统计一下把 $n$ 个点分成 $m$ 个环，有多少种方案。

再对于上一步的每一种方案，把这 $m$ 个环拼成一个生成树，有多少种方案。

对于第二步，结合 Prufer 编码，如果每次去掉一个部分，Prufer 编码的长度会是 $m - 2$，然后对于每个删去的环，由于这个环相邻的环内部会有很多点，我们删去的这个环可能连接任意一个点，这都会导致我们输出的 Prufer 编码不同，每次的输出都可能有 $n$ 种，因此 $n$ 个点分成 $m$ 个环能拼成的生成树的方案是 $n^{m-2}$ 种

接下来的需要知道第一步的方案数，即把 $n$ 个点分成 $m$ 个环的方案数。这里就要用计数类 dp 来求了。

设 $f[i][j]$ 表示把 $i$ 个点分成 $j$ 个环的方案数。

对于计数类 dp，我们通常需要围绕一个 “基准点” 来求，能避免子问题之间的重叠。我们以 $1$ 号点为 “基准点”，枚举 $1$ 号点所在的环的大小 $k$，从 $2 \sim i$ 这 $i - 1$ 个节点中选 $k - 1$ 个，然后对于 $k$ 个点的圆环，内部又有若干种组合方案，首先 $k$ 个点的排列有 $k!$ 种，且对称的和旋转的其实都是都一种，因此内部方案数为 $\frac{k!}{2*k}=\frac{(k-1)!}{2}$，并且这个环还需要连出来一条边用来和图中其他部分相连，这条边的选择也会有 $k$ 种，所以得出整个的方案数为 $f[i-k][j-1] * C_{i-1}^{k-1} * \frac{k!}{2}$

得出状态转移方程为：$f[i][j] = \sum_{k=1}^{i-j+1} f[i-k][j-1] * C_{i-1}^{k-1} * \frac{k!}{2}$

求出所有的 $f[i][j]$ 后，枚举一下分成的环的数量 $k$，分成 $k$ 个环的方案数是 $f[n][k]$，$k$ 个环拼成生成树的方案数是 $n^{k-2}$，所以最终答案就是 $\sum_{k=1}^{n} f[n][k] * n^{k-2}$。

注意，这里还有特殊情况需要处理，对于 $k$ 个点的环，由于还有向外连的一条边，所以我们求的方案数为 $\frac{(k-1)!}{2} *k = \frac{k!}{2}$，但是当 $k=1$ 时，也就是只有一个 $n$ 个节点的环时，我们没有向外连的这条边，且不需要求第二步，所以总方案数直接就是 $\frac{(n-1)!}{2}$

另外，由于本题是无向图且不存在重边，因此两个点之间是不存在环的，也需要特判一下

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 210;

int n, m;
int C[N][N]; //C(a, b)
int g[N]; //g[k] = k! / 2
int f[N][N]; //设 f[i][j] 表示把 i 个点分成 j 个环的方案数

void init() //预处理 C[][], g[]
{
    //预处理 C[][]
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= i; j++)
            if(!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;

    //预处理 g[]
    g[1] = 1, g[2] = 0, g[3] = 3;
    for(int i = 4; i <= n; i++) g[i] = g[i - 1] * i % m; //g[3] 已经除 2，后面都是乘法递推，除 2 是继承的
}

int main()
{
    scanf("%d%d", &n, &m);

    init(); //预处理 C[][], g[]

    //dp
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            for(int k = 1; k <= i - j + 1; k++)
                f[i][j] = (f[i][j] + (LL)f[i - k][j - 1] * C[i - 1][k - 1] * g[k]) % m; //状态转移方程

    int res = g[n - 1]; //统计总方案数，k = 1 时的方案数单独计算
    int p = 1; //记录 n 的 k - 2 次方
    for(int k = 2; k <= n; k++)
    {
        res = (res + (LL)f[n][k] * p) % m;
        p = (LL)p * n % m;
    }
    printf("%d\n", res);

    return 0;
}