\(\mathcal{Description}\)
link.
给一个 \(n\) 个点 \(m\) 条边的无向图 \(G\)。设图上有 \(k\) 个连通块，求出添加 \(k-1\) 条边使得这些连通块全部连通的方案数。对给定的 \(p\) 取模。
\(n,m\le10^5\)。
\(\mathcal{Solution}\)
\(\text{Prufer}\) 序列，设第 \(i\) 个连通块（可能是单点）的度数为 \(d_i\)，大小为 \(s_i\)。考虑连通块都是单点，方案数为：
\[k-2\choose d_1-1,d_2-1,\cdots,d_k-1
\]
即 \(k-2\) 个可重元素的排列数。接下来考虑连通块的大小，每个连通块都可以选出一个点来连边。所以方案数应乘上 \(s_i^{d_i}\)。那么方案数：
\[{k-2\choose d_1-1,d_2-1,\cdots,d_k-1}\prod_{i=1}^ks_i^{d_i}
\]
枚举 \(t_i=d_i-1\)：
\[\sum_{t_i\ge0\land\sum t_i=k-2}{k-2\choose t_1,t_2,\cdots,t_k}\prod_{i=1}^ks_i^{t_i+1}
\]
发现有一个 \(k\) 元多项式 \(\sum_{i=1}^ks_i\) 的 \(k-2\) 次方，提出来：
\[\left(\sum_{i=1}^ks_i\right)^{k-2}\prod_{i=1}^ks_i
\]
显然 \(\sum_{i=1}^ks_i=n\)，所以答案：
\[n^{k-2}\prod_{i=1}^ks_i
\]
\(\mathcal{Code}\)
为什么不直接打并查集啊喂。
#include <cstdio>
#include <vector>
const int MAXN = 1e5, MAXM = 1e5;
int n, m, p, ecnt, head[MAXN + 5];
std::vector<int> siz;
bool vis[MAXN + 5];
struct Edge { int to, nxt; } graph[MAXM * 2 + 5];
inline void link ( const int s, const int t ) { graph[++ ecnt] = { t, head[s] }, head[s] = ecnt; }
inline int qkpow ( int a, int b ) {
int ret = 1;
for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;
return ret;
}
inline int DFS ( const int u ) {
if ( vis[u] ) return 0;
int ret = vis[u] = true;
for ( int i = head[u]; i; i = graph[i].nxt ) ret += DFS ( graph[i].to );
return ret;
}
int main () {
scanf ( "%d %d %d", &n, &m, &p );
if ( p == 1 ) return puts ( "0" ), 0;
for ( int i = 1, u, v; i <= m; ++ i ) {
scanf ( "%d %d", &u, &v );
link ( u, v ), link ( v, u );
}
int ans = 1;
for ( int i = 1, t; i <= n; ++ i ) {
if ( ! vis[i] ) {
siz.push_back ( t = DFS ( i ) );
ans = 1ll * ans * t % p;
}
}
if ( siz.size () == 1 ) return puts ( "1" ), 0;
ans = 1ll * ans * qkpow ( n, siz.size () - 2 ) % p;
printf ( "%d\n", ans );
return 0;
}
