Prufer 序列

Statement

CodeForces 156D

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

\(n,m\le 10^5\)

Solution

我们假装现在是 \(k\) 个点，想要联通的方案数，

知道一棵无根树唯一对应一个 prufer 序列，prufer 序列长 \(k-2\) ，每一个位置随便填，所以有方案数 \(k^{k-2}\) ，知道一个数在 prufer 序列中出现次数于度数相关

但我们现在是联通块，设连通块 \(i\) 大小 \(siz[i]\) ，在生成树度数 \(d[i]\) 方案数即是

\[\binom{k-2}{d_1-1,d_2-1,\dots ,d_k-1} \prod siz_i^{d_i} \]

即是说我们先把同一个联通块的点看成本质相同的，所以得到一个多重集排列数

但是实际连边的时候是有区分的，所以我们乘上一个 \(\prod\)

由于我们并不知道度数具体是多少，令 \(t_i=d_i-1\) ，我们枚举一下度数

\[\sum_{\sum t=k-2}\binom{k-2}{t_1,t_2,\dots ,t_k}\prod siz_i^{t_i+1} \]

这里给出多项式定理的形式：

\[(x_1+x_2+\dots+x_n)^m=\sum_{\sum t=m}\binom m{t_1,t_2,\dots ,t_n}\prod x_i^{t_i} \]

证明略去，感性理解一共有 \(m\) 个括号，要给每一个 \(x\) 分配次数，一共 \(m\) 次，分 \(n\) 份，多重集排列数

相比于多项式定理，我们这里仅仅式多了一个 \(\prod siz_i\) 提出后直接套：

\[\begin{align*} &\sum_{\sum t=k-2}\binom{k-2}{t_1,t_2,\dots ,t_k}\prod siz_i^{t_i+1}\\ =&(\sum siz_i)^{k-2}\prod siz_i\\ =&n^{k-2}\prod siz_i \end{align*} \]

直接计算输出即可

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;

// char buf[1<<23],*p1=buf,*p2=buf;
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

vector<int>Edge[N];
int n,m,p,siz,cnt,ans=1;
bool vis[N];

int ksm(int a,int b){
    int res=1%p;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p,b>>=1;
    }
    return res;
}
void dfs(int u){
    siz++,vis[u]=1;
    for(auto v:Edge[u])if(!vis[v])dfs(v);
}

signed main(){
    n=read(),m=read(),p=read();
    if(p==1)return puts("0"),0;
    for(int i=1,u,v;i<=m;++i)
        u=read(),v=read(),
        Edge[u].push_back(v),
        Edge[v].push_back(u);
    for(int i=1;i<=n;++i)if(!vis[i])
        cnt++,siz=0,dfs(i),(ans*=siz)%=p;
    if(cnt<2)printf("%lld\n",1%p);
    else printf("%lld\n",(ans*ksm(n,cnt-2))%p);
    return 0;
}