查看原题

点击加载点击跳转

设s_i为每个连通块点数

对每个连通块构建prufer序列

由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2

对于给定d序列构造prufer序列的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}

对于第i个连通块,它的连接方式有s_i^{d_i}种,对于给定d序列使图连通的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

枚举d序列:

\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

换元,设e_i=d_i-1:

\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}

根据多元二项式定理:

\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}

原式化简得:

\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i

即 \displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i

#include<bits/stdc++.h>
const int N=100011;
int n,m,p,f[N],s[N];
int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}
int pw(int x,int b){
    int res=1;
    for(;b;b>>=1,x=1ll*x*x%p)
        if(b&1)res=1ll*res*x%p;
    return res;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    if(p==1)return puts("0"),0;
    int x,y,ans=1,k=0;
    for(int i=1;i<=n;++i)f[i]=i;
    for(int i=1;i<=m;++i)
        scanf("%d%d",&x,&y),f[gf(x)]=gf(y);
    for(int i=1;i<=n;++i)++s[gf(i)];
    for(int i=1;i<=n;++i)
        if(i==f[i])ans=1ll*ans*s[i]%p,++k;
    if(k==1)puts("1");
    else printf("%d\n",1ll*pw(n,k-2)*ans%p);
}