详见Prufer编码例题

Problem

题目描述

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

输入格式

第一行为$N(0\lt N\le 1000)$，接下来$N$行，第$i+1$行给出第$i$个节点的度数$D_i$，如果对度数不要求，则输入-1

输出格式

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

输入

1
2
3
4
3
1
-1
-1

输出

1
2

说明/提示

两棵树分别为1-2-3;1-3-2

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct bigint
{
	mutable int a[1005];
	inline int& operator[](size_t pos)const{return a[pos];}
	inline bigint(){memset(a,0,sizeof(a));a[0]=1;}
	inline bigint& operator*=(int b)
	{
		int i;
		for(i=1;i<=a[0];++i)a[i]*=b;
		for(i=1;i<=a[0]||a[i];++i)
		{
			if(a[i]>=10000)
			{
				a[i+1]+=a[i]/10000;
				a[i]%=10000;
			}
		}
		a[0]=i-1;
		return *this;
	}
}ans;
inline ostream& operator<<(ostream& os,const bigint& a)
{
	printf("%d",a[a[0]]);
	for(int i=a[0]-1;i>=1;--i)printf("%04d",a[i]);
	return os;
}
int num[1005],d[1005],p[1005],cnt;
bool vis[1005];
inline void Solve(int x,int del)
{
	int i,j,s;
	for(i=1;i<=cnt&&p[i]<=x;++i)
	{
		s=p[i];
		while(s<=x)
		{
			num[i]+=(x/s)*del;
			s*=p[i];
		}
	}
	return;
}
inline void Init()
{
	int i,j;
	for(i=2;i<=1000;++i)
	{
		if(!vis[i])p[++cnt]=i;
		for(j=1;j<=cnt&&i*p[j]<=1000;++j)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
	return;
}
int main(void)
{
	Init();
	int i,j,n,m=0,sum=0;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&d[i]);
		if(d[i]==-1)++m;
		else
		{
			--d[i];sum+=d[i];
		}
	}
	if(sum>n-2){printf("0\n");return 0;}
	Solve(n-2,1);
	Solve(n-sum-2,-1);
	for(i=1;i<=n;++i)
	{
		if(d[i]>0)Solve(d[i],-1);
	}
	ans[1]=1;
	for(i=1;i<=cnt;++i)
	{
		for(j=1;j<=num[i];++j)ans*=p[i];
	}
	for(i=1;i<=n-sum-2;++i)ans*=m;
	cout<<ans<<endl;
	return 0;
}