Bzoj 1211: [HNOI2004]树的计数 prufer序列

2018-05-17

既然我们知道每个点的度数,那我们就知道每个点在prufer序列中出现了多少次。

所以答案就是\(\left ( n-2 \right )!/\prod_{i=1}^n(d[i]-1)!\)。

直接程会爆long long,所以我们就求每个质因子对答案的贡献。

有一些细节需要注意,看代码好了。

Description

一个有n个结点的树,设它的结点分别为v1, v2, …, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵。给定n,d1, d2, …, dn,编程需要输出满足d(vi)=di的树的个数。

Input

第一行是一个正整数n,表示树有n个结点。第二行有n个数,第i个数表示di,即树的第i个结点的度数。其中1<=n<=150,输入数据保证满足条件的树不超过10^17个。

Output

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

Sample Input

4
2 1 2 1

Sample Output

2

Leave a Reply:

电子邮件地址不会被公开。 必填项已用*标注