题目大意

给定一个 n 个点 m 条边的带标号无向图，它有 k 个连通块，求添加 k-1 条边使得整个图连通的方案数，答案对 p 取模。(1 \le n \le 10^5, 0 \le m \le 10^5, 1 \le k \le 10^9)

解题思路

设 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)!}

由于每个联通块，向外连 1 条边的方案为 s_i 种，度数为 d_i 的联通块向外连接 d_i 条边的方案数即为 {s_i}^{d_i}。因此对于给定的 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)^n = \sum_{c_i \ge 0,\sum_{i=1}^m c_i = n}\binom{n}{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

可以使用并查集维护联通快的大小。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
int n, m, P;
int ans = 1;

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}

int f[N], sz[N];
int find(int x) {
    return f[x] == x ? x : (f[x] = find(f[x]));
}

int main(int argc, const char * argv[]) {
    scanf("%d%d%d", &n, &m, &P);
    for (int i = 1; i <= n; i++) {
        f[i] = i;
    }
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        f[find(a)] = find(b);
    }
    for (int i = 1; i <= n; i++) {
        sz[find(i)]++;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == find(i)) {
            cnt++;
            ans = 1LL * ans * sz[i] % P;
        }
    }
    if (cnt == 1) ans = 1 % P;
    else ans = 1LL * ans * ksm(n, cnt - 2) % P;
    printf("%d\n", ans);
    return 0;
}