题解 CF156D 【Clues】
xht
2020-02-10 22:04:26
# 请在博客中查看
设 $s_i$ 为第 $i$ 个连通块的点数，$d_i$ 为第 $i$ 个连通块的度数。
对于给定的 $d$ 序列构造 Prufer 序列的方案数为：
$$
\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}=\frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdots(d_k-1)!}
$$
对于给定的 $d$ 序列使图连通的方案数为：
$$
\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot\prod_{i=1}^k{s_i}^{d_i}
$$
枚举 $d$ 序列使图连通的方案数为：
$$
\sum_{d_i\ge 1,\sum_{i=1}^kd_i=2k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\cdot\prod_{i=1}^k{s_i}^{d_i}
$$
设 $e_i=d_i-1$：
$$
\sum_{e_i\ge 0,\sum_{i=1}^ke_i=k-2}\binom{k-2}{e_1,e_2,\cdots,e_k}\cdot\prod_{i=1}^k{s_i}^{e_i+1}
$$
考虑多元二项式定理：
$$
(x_1 + \dots + x_m)^p = \sum_{c_i \ge 0,\sum_{i=1}^m c_i = p}\binom{p}{c_1, c_2, \cdots ,c_m}\cdot \prod_{i=1}^m{x_i}^{c_i}
$$
原式变为：
$$
(s_1+s_2+\cdots+s_k)^{k-2}\cdot\prod_{i=1}^ks_i
$$
即：
$$
n^{k-2}\cdot\prod_{i=1}^ks_i
$$
```cpp
const int N = 1e5 + 7;
int n, m, k, f[N], s[N];
modint ans = 1;
int get(int x) {
return x == f[x] ? x : (f[x] = get(f[x]));
}
int main() {
rd(n), rd(m), rd(P);
if (P == 1) return print(0), 0;
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), f[get(x)] = get(y);
for (int i = 1; i <= n; i++) ++s[get(i)];
for (int i = 1; i <= n; i++) if (i == get(i)) ++k, ans *= s[i];
if (k == 1) return print(1), 0;
print(ans *= (modint)n ^ (k - 2));
return 0;
}
```