树的计数 bzoj-1211 HNOI-2004

题目大意：题目链接。

注释：略。

想法：

prufer序列有一个性质就是一个数在prufer序列中出现的次数等于这个prufer序列生成的树中它的度数-1。

故此我们就是要求$C_{n-2}^{d_1-1}\times C_{n-2-d_1+1}^{d_2-1}\times \cdots \times C_{d_n-1}^{d_n-1}$。

随便搞搞就行了。

Code：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 160

using namespace std;

typedef long long ll;

int n,sum,d[M];

int cnt[M];

ll ans=1;

ll Quick_Power(ll x,int y)

{

	ll re=1;

	while(y)

	{

		if(y&1)re*=x;

		x*=x;

		y>>=1;

	}

	return re;

}

void Decomposition(int x,int flag)

{

	int i;

	for(i=2;i*i<=x;i++)

		while(x%i==0)

			cnt[i]+=flag,x/=i;

	if(x^1)

		cnt[x]+=flag;

}

int main()

{

	int i,j;

	cin>>n;

	for(i=2;i<=n-2;i++)

		Decomposition(i,1);

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

	{

		scanf("%d",&d[i]);

		if(!d[i]&&n!=1)

		{

			puts("0");

			return 0;

		}

		sum+=d[i]-1;

		for(j=2;j<=d[i]-1;j++)

			Decomposition(j,-1);

	}

	if(sum!=n-2)

	{

		puts("0");

		return 0;

	}

	for(i=1;i<=n-2;i++)

		if(cnt[i])

			ans*=Quick_Power(i,cnt[i]);

	cout<<ans<<endl;

}

小结：prufer序列好像只有裸题诶.....

巴特西

[bzo1211][HNOI2004]树的计数_prufer序列

树的计数 bzoj-1211 HNOI-2004

最新文章

热门文章