P2290 [HNOI2004]树的计数（bzoj1211）

洛谷P2290 [HNOI2004]树的计数

 bzoj1211 [HNOI2004]树的计数

Description

一个有\(n\)个结点的树，设它的结点分别为\(v_1,v_2,\cdots, v_n\)，已知第\(i\)个结点\(v_i\)的度数为\(d_i\)

问满足这样的条件的不同的树有多少棵。

Input

第一行是一个正整数\(n\)，表示树有\(n\)个结点。第二行有\(n\)个数，第\(i\)个数表示\(d_i\)，即树的第\(i\)个结点的度数。其中\(1\le n\le 150\)，输入数据保证满足条件的树不超过\(10^{17}\)个。

Output

输出满足条件的树有多少棵。

可以说是个模板题

prufer 编码，这里只给结论，证明去这里看

我不想复制一遍了

注意一下以下说的“种”和“个”是不同的

由于 prufer 编码的一些性质，其实问题求的就是，总共\(n-2\)个元素，其中有\(n\)种不同元素，每种元素有\(d_i-1\)个，的排列数

所以，如果\(\sum_{i+1}^nd_i-1\neq n-2\)或者\(d_i=0\)则无解，不过要特判\(n=1\)的情况

如何证明在那个链接里都有

首先如果没有这个每种元素多少个的条件，那么\(n-2\)个元素的排列数就是\((n-2)!\)

然后要去重，因为对于每一种元素，这\(d_i-1\)个元素无论怎么变换顺序都是算一种，所以当然要除以\((d_i-1)!\)

那么答案就是：

\[\frac{(n-2)!}{\prod_{i=1}^n d_i-1}
\]

但是题目保证的是最后结果不大于\(10^{17}\)，所以中间值可能会爆\(long long\)

那么我们采取分解质因数的方法，最后再乘起来

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	register int x=0;register int y=1;

	register char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n;

int prime[155],notprime[155];

inline void get_prime(){

	for(reg int i=2;i<=n;i++){

		if(notprime[i]) continue;

		prime[++prime[0]]=i;

		for(reg int j=i+i;j<=n;j+=i) notprime[j]=1;

	}

}

int num[155],d[155];

inline void mul(int x,int k){

	for(reg int i=1;i<=prime[0];i++)

		while(!(x%prime[i])) num[i]+=k,x/=prime[i];

}

int main(){

	n=read();

	if(n==1){

		d[1]=read();

		return std::puts(d[1]?"0":"1"),0;

	}

	get_prime();

	int sum=0;

	for(reg int i=1;i<=n;i++){

		sum+=d[i]=read()-1;

		if(d[i]==-1) return std::puts("0"),0;

	}

	if(sum!=n-2) return std::puts("0"),0;

	for(reg int i=1;i<=n-2;i++) mul(i,1);

	for(reg int i=1;i<=n;i++)

		for(reg int j=1;j<=d[i];j++) mul(j,-1);

	LL ans=1;

	for(reg int i=1;i<=prime[0];i++)

		for(reg int j=1;j<=num[i];j++) ans*=prime[i];

	std::printf("%lld",ans);

	return 0;

}

巴特西

P2290 [HNOI2004]树的计数（bzoj1211）

Description

Input

Output

最新文章

热门文章