Codeforces

Luogu

分析

我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为
$$
\sum_{d_i\geq 1,\sum_{i=1}^k d_i=2k-2}\frac{(k-2)!}{\prod_{i=1}^k(d_i-1)!}
$$
但这并不是答案，因为对于每个连通块的每条边我们都需要选一个点作为端点。设 $s_i$ 为第 $i$ 个联通块的大小，则答案为
$$
\sum_{d_i\geq 1,\sum_{i=1}^k d_i=2k-2}\frac{(k-2)!}{\prod_{i=1}^k(d_i-1)!}\prod_{i=1}^ks_i^{d_i}
$$
利用广义二项式定理可以化简为
$$
\left(\sum_{i=1}^k s_i\right)^{k-2}\prod_{i=1}^ks_i
$$
即
$$
n^{k-2}\prod_{i=1}^k s_i
$$
用并查集求出连通块个数及每个连通块的大小即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int mod;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void merge(int u,int v) {
    u=find(u),v=find(v);
    if (u!=v) f[u]=v;
}

int n,m,k,s[N];

int main() {
    n=read(),m=read(),mod=read(); int ans=1;
    if (mod==1) { puts("0"); return 0; }
    for (int i=1;i<=n;++i) f[i]=i;
    for (int i=1;i<=m;++i) merge(read(),read());
    for (int i=1;i<=n;++i) ++s[find(i)];
    for (int i=1;i<=n;++i) if (i==find(i)) ++k,ans=1ll*ans*s[i]%mod;
    if (k==1) { puts("1"); return 0; }
    else ans=1ll*ans*qpow(n,k-2)%mod;
    printf("%d\n",ans);
    return 0;
}