题解 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

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;
}