OI - Clues(Codeforces) | Lucky

prufer 和指数型生成函数结合的快乐结论题 :)

# 题面

点击展开/折叠题面

给定一个 $n$ 个点 $m$ 条边的带标号无向图。设此时图中有 $k$ 个连通块，求加入 $k-1$ 条边使得整张图连通的方案数。（对一个整数 $p$ 取模）

# 解析

假如原图上没有边，那么用 prufer数列的结论，就是 $n^{n-2}$。

当原图上有 $k$ 个连通块是否方案就是 $k^{k-2}$？我们发现如果是大小分别为 $A,B$ 的两个连通块相连，方案数是 $A\times B$（任意选择一对点）。

再进一步，我们发现如果在生成树中，连通块 $i$ 的大小为 $s_i$，它的度数（指生成树中从其他连通块连向连通块 $i$ 的边数）为 $d_i$。那么连通块 $i$ 对答案的贡献是 $s_i^{d_i}$——因为任意一条连向它的边都可以以 $s_i$ 个点中的任意一个点作为一个端点。

那么这种生成树的总方案数就是：

$\frac{(n-2)!}{\prod (d_i-1)!}\times \prod_is_i^{d_i}=(n-2)!\times\prod_{i}\frac{s_i^{d_i}}{(d_i-1)!}$

这个式子怎么算呢？我们发现后面的 prod 看起来很像指数型生成函数，再改一下：

$(n-2)!\times\prod_{i}s_i\times\prod\frac{s_i^{d_i-1}}{(d_i-1)!}$

而我们知道 $\sum(d_i-1)=n-2$（prufer数列有n-2项），所以可以用生成函数表达：

$\begin{split} &(n-2)!\times\prod s_i\times\left\{\prod\left(1+\frac{s_i}{1!}x+\frac{s_i^2}{2!}x^2\dots\right)\right\}[x^{n-2}]\\ =&(n-2)!\times\prod s_i\times\left\{\prod e^{s_ix}\right\}[x^{n-2}]\\ =&(n-2)!\times\prod s_i\times \left\{e^{(\sum s_i)x}\right\}[x^{n-2}]\\ =&(n-2)!\times\prod s_i\times\frac{(\sum s_i)^{n-2}}{(n-2)!}\\ =&\prod s_i\times\left(\sum s_i\right)^{n-2} \end{split}$

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10;

struct DSU{
	int fa[N];
	int FindFa(int u){return fa[u]==u? u:fa[u]=FindFa(fa[u]);}
	bool Merge(int u,int v){
		u=FindFa(u),v=FindFa(v);
		if(u==v) return false;
		fa[u]=v;
		return true;
	}
	void Init(int siz){
		for(int i=0;i<=siz;i++)
			fa[i]=i;
	}
};
DSU Ds;

int n,m,mod,cnt,sum,prd;
int siz[N];

#define cs const int &
inline int Add(cs a,cs b){return a+b>=mod? a+b-mod:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+mod:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%mod;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

inline int Ri(){
	register int a=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
	return a;
}
int main(){
	n=Ri(),m=Ri(),mod=Ri();
	Ds.Init(n);
	for(int i=1;i<=m;i++) Ds.Merge(Ri(),Ri());
	for(int i=1;i<=n;i++) siz[Ds.FindFa(i)]++;
	prd=1;
	for(int i=1;i<=n;i++)
		if(siz[i]){
			prd=Mul(prd,siz[i]);
			sum=Add(sum,siz[i]);
			cnt++;
		}
	if(cnt==1) printf("%d\n",1%mod);
	else printf("%d\n",Mul(prd,Pow(sum,cnt-2)));
	return 0;
}

THE END

Thanks for reading!

$\begin{split} “\ &悍戾滚热冲破枪口\\ &呼啸耳鸣震碎了刀锋\\ &利刃硝烟擦肩而过\\ &也形影紧扣依偎相拥\ ”\\ ——&\text{《无人赞颂的旅程》By 泠鸢yousa/Days} \end{split}$

> 《无人赞颂的旅程》- 网易云