【bzoj1005】[HNOI2008]明明的烦恼 Prufer序列+高精度

题目描述

给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

输入

第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

输出

一个整数,表示不同的满足要求的树的个数,无解输出0

样例输入

3
1
-1
-1

样例输出

题解

Prufer序列+高精度

Prufer序列：由一棵 $n$ 个点的树唯一产生的一个 $n-2$ 个数的序列。

生成方法：找到这棵树编号最小的叶子节点，将其相邻点加入到序列中，删掉这个点。重复这个过程直到树中只剩下两个点，此时得到的序列即为该树的Prufer序列。

性质：任何一个长度为 $n-2$ ，每个数均在 $1\sum n$ 之间的序列均为一个合法的Prufer序列，对应且只对应着一棵 $n$ 个点的树。

性质：在原树中度数为 $d$ 的点，在Prufer序列中出现了 $d-1$ 次。

根据这两个性质可以考虑本题。给出了每个点的度数限制，即给出了每个点在Prufer序列中出现的次数。对于没给限制的，可以随意选择。

相当于先在 $n-2$ 个数中选出一部分作为没有限制的，剩下的是有限制的。

对于没有限制的，答案就是 $没限制的位置个数^没限制的点的个数$ 。

对于有限制的，使用组合数学的一个公式：长度为 $\sum a_i$ 的序列，第 $i$ 个数出现了 $a_i$ 次的序列数为 $\frac{(\sum a_i)!}{\prod(a_i!)}$ 。

本题不取模，为避免高精度除法，将阶乘分解质因数来处理。

注意特判无解的情况。

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mod 100000000

using namespace std;

typedef long long ll;

struct data

{

	int len;

	ll v[400];

	ll &operator[](int a) {return v[a];}

	data operator+(data &a)

	{

		data ans;

		memset(ans.v , 0 , sizeof(ans.v));

		int i;

		for(i = 0 ; i < len || i < a.len || ans[i] ; i ++ )

			ans[i] += v[i] + a[i] , ans[i + 1] = ans[i] / mod , ans[i] %= mod;

		ans.len = i;

		return ans;

	}

	data operator*(int a)

	{

		data ans;

		memset(ans.v , 0 , sizeof(ans.v));

		int i;

		for(i = 0 ; i < len || ans[i] ; i ++ )

			ans[i] += v[i] * a , ans[i + 1] = ans[i] / mod , ans[i] %= mod;

		ans.len = i;

		return ans;

	}

	void write()

	{

		int i;

		printf("%lld" , v[len - 1]);

		for(i = len - 2 ; ~i ; i -- ) printf("%08lld" , v[i]);

		puts("");

	}

}ans;

int a[1010] , cnt[1010] , prime[1010] , tot , np[1010];

void init()

{

	int i , j;

	for(i = 2 ; i <= 1000 ; i ++ )

	{

		if(!np[i]) prime[++tot] = i;

		for(j = 1 ; j <= tot && i * prime[j] <= 1000 ; j ++ )

		{

			np[i * prime[j]] = 1;

			if(i % prime[j] == 0) break;

		}

	}

}

void solve(int x , int a)

{

	int i , j;

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

		for(j = x / prime[i] ; j ; j /= prime[i])

			cnt[i] += a * j;

}

int main()

{

	init();

	int n , i , c1 = 0 , c2 = 0;

	scanf("%d" , &n);

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

	{

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

		if(a[i] > 0) c1 += a[i] - 1;

		else if(a[i] == -1) c2 ++ ;

		else

		{

			puts("0");

			return 0;

		}

	}

	if(c1 > n - 2)

	{

		puts("0");

		return 0;

	}

	solve(n - 2 , 1) , solve(n - 2 - c1 , -1);

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

		if(a[i] > 0)

			solve(a[i] - 1 , -1);

	ans[0] = ans.len = 1;

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

		while(cnt[i] -- )

			ans = ans * prime[i];

	for(i = 1 ; i <= n - 2 - c1 ; i ++ ) ans = ans * c2;

	ans.write();

	return 0;

}

巴特西

【bzoj1005】[HNOI2008]明明的烦恼 Prufer序列+高精度

最新文章

热门文章