题解 [Luogu P6596] How Many of Them
P8107
·
2022-06-02 23:30:05
·
题解
luogu link
部分表述来源于李煜东的《算法竞赛进阶指南》。
题意
求满足如下条件的无向连通图数量：
由 n 个节点组成，每个节点有编号，编号为 1\sim n ;
割边数量 \leq m 条；
无自环，无重边。
数据范围 2\leq n\leq50,0\leq m\leq \frac{n*(n-1)}2 ，输出答案对 10^9+7 取模的值。
题解
首先有个结论：
在无向图中，不含割边的极大连通子图称为双连通分量 。若把每个双连通分量看做一个节点，则所有双连通分量和割边构成一棵树。
很容易理解：如果最后不构成树（有环），则环上的所有双连通分量必定能构成一个更大的双连通分量。
设 f_{i,j} 表示 i 个点包含 j 条割边的无向连通图数量j>0 （下面解释为什么）。
计数 dp 有个思想：“围绕基准点构造一个整体”。我们以编号为 1 的节点为“基准点”，枚举 1 所在双连通分量节点数 k 。这个双连通方案的构造方案数为 f_{k,0}*\binom{i-1}{k-1} （i-1 个节点选 k-1 个与 1 构成大小为 k 的双连通分量）。
如果 j=0 ，那么 k 只能取 i 按照上式，f_{i,j}=f_{k,0}*\binom{i-1}{k-1} ，我等于我自己了。
现在不考虑 j=0 ，考虑图中其他部分。去掉 1 号节点所在的双连通分量，无向图会分成若干连通块，从每个连通块出发都有一条边连接到 1 号点所在的双连通分量上（这条边即为割边）。
设 g_{i,j,k} 表示 i 个点包含 j 条割边的有 k 个连通块的“有根”无向图数量1 号点所在的双连通分量连边的那个节点。在此处处理更加简便。则去掉 1 号点所在的双连通分量后，图中剩余部分方案数为 g_{i-k, j-x,x} ，其中 x 表示剩余连通块个数。因为 1 号点所在的双连通分量有 k 个节点，所以 x 个连通块连接上去，共有 k^x 中方案。
综上，f_{i,j}(0<j<i) 的转移方程：
f_{i,j} = \sum\limits_{k=1}^{i-1} \left(f_{k,0}* \dbinom{i-1}{k-1}*\sum_{x=1}^{\min(i-k,j)}\left(g_{i-k,j-x,x}* k^x\right)\right)
设 h_i 表示 i 个节点的无向连通图数量，则 f_{i,0}=h_i-\sum\limits_{j=1}^{i-1}f_{i,j} 。
现在考虑 h_i,g_{i,j,k} 怎么求。
首先是 h_i ：
求连通图个数不好求，考虑求不连通图个数。则 dp_i=all_i-notConnected_i 。
$$h_i=2^{\binom i2}-\sum\limits_{j=1}^{i-1}\dbinom{i-1}{j-1}* h_j*2^{\binom{i-j}2}$$
------
$g_{i,j,k}$（$i$ 个点包含 $j$ 条割边的有 $k$ 个连通块的“有根”无向图数量）：
以编号最小的节点所在连通块为基准，枚举该连通块大小 $p$，割边数量 $q$。该连通块的方案有 $f_{p,q}* \binom{i-1}{p-1}$ 种；选连通块中的“根”，有 $p$ 中选法；其它部分的方案数是 $g_{i-p,j-q,k-1}$。得到方程：
$$g_{i,j,k}=\sum\limits_{p=1}^i\sum_{q=0}^{j^*}f_{p,q}* \dbinom{i-1}{p-1}* p* g_{i-p,j-q,k-1}$$
$^*$：这里应该是 $j$，但蓝书写成了 $k$。
------
接下来就是代码细节了。我们可以首先枚举 $i$，接着按 $h_i,f_{i,j(j>0)},f_{i,0},g_{i,j,k}$ 的顺序计算，可以保证每个状态都恰好更新到。
然后就是一些边界问题：
$f_{i,j(j>0)}$ 中的 $j$ 的范围当然是 $(0,i)$，$g_{i,j,k}$ 中的 $j,k$ 呢？$j$ 是割边数，自然不可能取到 $i$，范围 $[0,i)$；$k$ 是连通块个数，不可能是 $0$，范围 $[1,i]$。还要注意一个初始化：$g_{0,0,0} = 1$。这个应该很容易想到，因为如果没有初始化那么算出来的所有 $g$ 都是 $0$，于是套路地初始化 $g_{0,0,0}$。
## 代码
```cpp
//acwing308
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 60; const ll P = 1e9 + 7;
ll A[N], invA[N], h[N], f[N][N], g[N][N][N], ans;
int n, m;
ll qp(ll a, ll b){ ll r=1; while(b){ if(b&1) r=r*a%P; a=a*a%P; b>>=1; } return r; }
ll C(int n, int m){ return A[n] * invA[m] % P * invA[n-m] % P; }
int main(){
scanf("%d%d", &n, &m); if(m > n) m = n;
A[0] = 1, invA[0] = 1, g[0][0][0] = 1;
for(int i = 1; i <= n; ++ i) A[i] = A[i-1] * i % P, invA[i] = qp(A[i], P-2);
for(int i = 1; i <= n; ++ i){
h[i] = qp(2, C(i, 2));
for(int j = 1; j < i; ++ j)
h[i] = (h[i] - h[j] * C(i-1, j-1) % P * qp(2, C(i-j, 2)) % P + P) % P;
for(int j = 1; j < i; ++ j)
for(int k = 1; k < i; ++ k){
ll tmp = 0;
for(int x = 1; x <= min(i-k, j); ++ x)
tmp = (tmp + g[i-k][j-x][x] * qp(k, x) % P) % P;
f[i][j] = (f[i][j] + f[k][0] * C(i-1, k-1) % P * tmp % P) % P;
}
f[i][0] = h[i];
for(int j = 1; j < i; ++ j) f[i][0] = (f[i][0] - f[i][j] + P) % P;
for(int j = 0; j < i; ++ j)
for(int k = 1; k <= i; ++ k)
for(int p = 1; p <= i; ++ p)
for(int q = 0; q <= j; ++ q)
g[i][j][k] = (g[i][j][k] + f[p][q] * C(i-1, p-1) % P * p % P * g[i-p][j-q][k-1] % P) % P;
}
for(int i = 0; i <= m; ++ i) ans = (ans + f[n][i]) % P;
printf("%lld\n", ans);
return 0;
}
```