解法

（参考蓝书与部分其它题解以及部分评论）。

首先考虑设计状态 $f_{i,j}$ 表示 $i$ 个点，且共有 $j$ 条割边的无向连通图的数量。

然后接下来我们需要讨论 $f_{i,j}$ 的状态转移方程。

首先对于 $f_{i,0}$，实际上就是所有无向连通图的数量 $h_{i}$ 减去 $\sum_{k=1}^{i-1} f_{i,k}$，剩下的就只能是 $f_{i,0}$。但是此时我们发现 $0$ 要从 $j(j>0)$ 转移，这个顺序有点烦人，先不管了，把式子写在下面：

$$ \begin{aligned} f_{i,0}=h_{i}-\sum_{k=1}^{i-1} f_{i,k} \end{aligned} $$

然后考虑 $j>0$ 的转移方程，有割边意味着有几个强连通分量，由于所有我们区分编号，所以枚举 $1$ 所在的强连通分量的大小 $k$，这样的方案数是 $f_{k,0}\times {i-1 \choose k-1}$，意思是，我们除了 $1$ 点还需要选 $k-1$ 个点，然后从 $i-1$ 个点里选。这里惊奇的发现，我们不需要从 $f_{i,0}$ 来转移，因此说明我们可以忍受上面的转移。这里留下一个问题：为什么我们不能直接枚举任意一个连通块的大小，即 ${i \choose k}$？

原因是，我们要做到不重不漏，如果我们只考虑每次选走的是哪些，就会出现这种情况：假设我们有 $5$ 个点，第一次选 $1,2,3$，第二次选 $4,5$，然后又有一种选法，第一次选 $4,5$ 与 $1,2,3$。容易看出，这两种是同一种情况，所以我们多算了。但是如果每次包含点 $1$ 的话，我们就不会出现刚刚的情况，因为我们对于 $1$ 点的连通块大小不同，所以分配也不会相同，同时，容易知道这样我们考虑了所有分法，所以也不会漏。实际上，我们所讲的 $1$ 点就是当前点中最小的点。

我们再来整理一遍，枚举 $1$ 所在的强连通分量的大小 $k$，这样的方案数是 $f_{k,0}\times {i-1 \choose k-1}$。那么我们还要处理非 $1$ 点所在连通块的方案数。我们设 $g_{i,j,k}$ 表示由 $i$ 个点组成的无向图，有 $j$ 个连通块，这些连通块中一共有 $k$ 条割边，并且算上每个块与 $1$ 所在的连通块相连的方案数，然后，我们还需要在 $1$ 所在的连通块中选择一个与其他连通块连接的点，每次有 $k$ 种选择。枚举剩余的连通块 $x$，那么根据乘法原理总共就有 $k^x$ 种选择方法。并且当剩余的连通块为 $x$ 时，剩余的图有 $g_{i-k,x,j-x}$ 种方案。我们先不管 $g_{i,j,k}$ 的计算方法，此时我们得到了 $f_{i,j}(j>0)$ 的计算方法：

$$ \small \begin{aligned} f_{i,j}=\sum_{k=1}^{i-1} f_{k,0}\times {i-1 \choose k-1} \times \sum_{x=1}^{\min(i-k,j)} g_{i-k,x,j-x} \times k^x \end{aligned} $$

现在来考虑 $h_{i}$ 的算法（无向连通图的数量）。正难则反，我们考虑用总共的无向图的数量减去不连通的图的数量，$i$ 个点的无向图，总共可以连 $i\times (i-1)\times \frac{1}{2}$ 条边，每条边可有可无，所以总个数为 $2^{i\times (i-1) \times \frac{1}{2}}$。再来考虑不连通的图的数量，仍然的，我们考虑一号点所在的连通块大小 $j$，选出另外 $j-1$ 个点，这个方案数为 ${i-1\choose j-1} \times h_{j}$，然后对于剩余的图，它是什么样子都可以，于是乘上 $2^{(i-j)\times (i-j-1) \times \frac{1}{2}}$。至此得到 $h_{i}$ 的转移式：

$$ \small \begin{aligned} h_{i}=2^{i\times (i-1) \times \frac{1}{2}}-\sum_{j=1}^{i-1} h_{j} \times {i-1 \choose j-1} \times 2^{(i-j)\times (i-j-1)\times \frac{1}{2}} \end{aligned} $$

好的，现在我们只差 $g_{i,j,k}$（由 $i$ 个点组成的无向图，有 $j$ 个连通块，这些连通块中一共有 $k$ 条割边的方案数）的转移式了。考虑同样 $1$ 号点的连通块的大小为 $p$，这个连通块所含割边数量为 $q$，我们同样要选择，在 $i-1$ 中，选择 $p-1$ 个点，因此方案数为 $f_{p,q}\times {i-1 \choose p-1}$。然后考虑其余部分的方案数其实就是 $g_{i-p,j-1,k-q}$。注意这里我们为了算出上文的每个块与 $1$ 在的连通块相连的方案数，需要乘 $p$。于是我们又得出了 $g_{i,j,k}$ 的状态转移方程。

$$ \begin{aligned} g_{i,j,k}=\sum_{p=1}^{i}\sum_{q=0}^{k} f_{p,q} \times {i-1 \choose p-1} \times g_{i-p,j-1,k-q} \times p \end{aligned} $$

接下来，我们还要讨论转移顺序，对于对于 $f_{i,j}$，它只需要 $g_{i-1,a,b}$ 就行了，也就是 $i-1$ 时的 $g$，我们可以假定 $i$ 从大到小循环，那么此时对于新的 $i$，我们直接计算 $f_{i,j}$ 就行了，因为它的 $g$ 以及 $f_{k,0}$ 在 $i’(i’<i)$ 时都已经计算过了，对于 $g$ 来说，它需要 $f_{a,b}(a\le i)$ 那么只需要在当前 $i$ 的 $f$ 计算过后转移 $g$ 即可（在这之前要转移 $f_{i,0}$）。

此时转移的初始条件为 $f_{1,0}=h_{1}$ 和 $g_{0,0,0}=1$。

至此，我们解决了这道题目。

注意不能根据 $m$ 缩小枚举范围！否则无法正确计算！我们需要完整的计算出一个状态！

Code

// Problem: P6596 How Many of Them
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6596
// Memory Limit: 32 MB
// Time Limit: 800000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 110, M = 1e5 + 10, X = 1e9 + 7;
int h[M], f[N][N], g[N][N][N], inv[M], fac[M];
int n, m;
int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % X;
        a = a * a % X;
        b >>= 1;
    }
    return res;
}
void init() {
    inv[0] = 1, fac[0] = 1;
    upp(i, 1, N - 1) {
        fac[i] = fac[i - 1] * i % X;
        inv[i] = qmi(fac[i], X - 2);
    }
    return;
}
int choose(int x, int y) {
    return fac[x] * inv[y] % X * inv[x - y] % X;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    init();

    upp(i, 1, n) {
        h[i] = qmi(2, i * (i - 1) / 2);
        upp(j, 1, i - 1) {
            h[i] =
                ((h[i] - h[j] * choose(i - 1, j - 1) % X * qmi(2, (i - j) * (i - j - 1) / 2) % X) % X +
                 X) %
                X;
        }
        f[i][0] = h[i];
    }
    // get h[i]

    g[0][0][0] = 1;
    upp(i, 1, n) {
        upp(j, 1, i - 1) {
            upp(k, 1, i - 1) {
                int tmp = f[k][0] * choose(i - 1, k - 1) % X, sum = 0;
                upp(x, 1, min(i - k, j))(sum += g[i - k][x][j - x] * qmi(k, x) % X) %= X;
                (tmp *= sum) %= X;
                (f[i][j] += tmp) %= X;
            }
            (((f[i][0] -= f[i][j]) %= X) += X) %= X;
        } // for f[i][j]

        upp(j, 1, i) {
            upp(k, 0, i - 1) {
                upp(p, 1, i) {
                    upp(q, 0, k) {
                        (g[i][j][k] +=
                         f[p][q] * choose(i - 1, p - 1) % X * g[i - p][j - 1][k - q] % X * p % X) %= X;
                    }
                }
            }
        }
    }
    // get g[i][j][k] and f[i][j]

    int ans = 0;
    upp(j, 0, m)(ans += f[n][j]) %= X;
    cout << ans << endl;
    return 0;
}