[HNOI2008]明明的苦恼 树的 prufer 编码

Description

自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
Input

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

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

这道题如果知道树的 prufer 编码就是裸题了。

树的 prufer 编码的构造其实很容易：每次选一个编号最小的叶子节点，将其父亲加入编码，再将其自己删掉即可。

然后从 prufer 编码到树的构造就是反过来。。。总之是一对一的映射了。。。显然每个点在序列中出现的次数为度数减一。

然后就等于求不同的数组的方案了。排列组合：m 为有度数限制的点的个数，sum 为所限制的度数和。

ans = (n - m) ^ (n - 2 - sum) * (n - 2) ! / (deg[1] ! * deg[2] ! * ... * deg[m] ! * (n - 2 - sum) !)。

然后懒得写高精除，于是分解质因数之。。。也不是很慢。。。

Code :

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define maxn 1000

struct longint {
	int a[maxn];
	int & operator [](const int & b) {return a[b];}
}	ans, kk;

void operator *=(longint & a, const int & b)
{
	int i;
	for (i = 1; i <= a[0]; ++ i) a[i] *= b;
	for (i = 1; i <= a[0]; ++ i)
		if (a[i] >= 10000) a[i + 1] += a[i] / 10000, a[i] %= 10000;
	if (a[a[0] + 1]) ++ a[0];
}

void print(longint & a)
{
	int i;
	printf("%d", a[a[0]]);
	for (i = a[0] - 1; i >= 1; -- i) printf("%04d", a[i]);
	puts("");
}

struct da {int s, t; da * n;} das[maxn * 30];
da * edge[maxn + 5], * adj = das;
int n, deg, rest, sum, tot;
int pm[maxn + 5], num[maxn + 5];
bool np[maxn + 5];

void prepare()
{
	int i, j, k;
	for (i = 2; i <= maxn; ++ i)
	{
		if (! np[i]) pm[++ tot] = i;
		for (j = 1; j <= tot; ++ j)
		{
			k = pm[j] * i;
			if (k > maxn) break; else np[k] = 1;
			if (i % pm[j] == 0) break;
		}
	}
	for (i = 1; i <= maxn; ++ i)
		for (j = 1; j <= tot; ++ j)
		{
			k = i;
			if (pm[j] > i) break;
			if (i % pm[j]) continue; else k = i / pm[j];
			* (++ adj) = (da) {1, j, edge[i]}, edge[i] = adj;
			for (; k % pm[j] == 0; k /= pm[j]) ++ adj->s;
		}
}

int main()
{
	freopen("1005.in", "r", stdin);
	freopen("1005.out", "w", stdout);
	
	int i, j; da * e;
	scanf("%d", & n), prepare();
	for (i = 1; i <= n; ++ i)
	{
		scanf("%d", & deg);
		if (~ deg)
			for (sum += deg - 1, j = 1; j < deg; ++ j)
				for (e = edge[j]; e; e = e->n) num[e->t] -= e->s;
		else ++ rest;
	}
	for (i = n - 2; i > n - 2 - sum; -- i)
		for (e = edge[i]; e; e = e->n) num[e->t] += e->s;
	for (e = edge[rest]; e; e = e->n)
		num[e->t] += (n - 2 - sum) * e->s;
	ans[0] = ans[1] = 1;
	for (i = 1; i <= tot; ++ i)
		for (j = 1; j <= num[i]; ++ j) ans *= pm[i];
	print(ans);
	
	return 0;
}