BZOJ 1005 [HNOI2008]明明的烦恼 (Prufer编码 + 组合数学 + 高精度)

时间:2023-03-08 16:55:10

1005: [HNOI2008]明明的烦恼

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 5786  Solved: 2263
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

3
1
-1
-1

Sample Output

2

HINT

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

Source

析:  转载:http://blog.****.net/popoqqq/article/details/40182169

把一棵树进行以下操作:

1.找到编号最小的叶节点,删除这个节点,然后与这个叶节点相连的点计入序列

2.反复进行1,直到这棵树只剩下两个节点时,退出

BZOJ 1005 [HNOI2008]明明的烦恼 (Prufer编码 + 组合数学 + 高精度)

比如说这个图(来自度受百科)

最小叶节点为2,删除2,将3计入序列

最小叶节点为4,删除4,将5计入序列

最小叶节点为5,删除5,将1计入序列

最小叶节点为1,删除1,将3计入序列

图中只剩下两个节点,退出

于是得到这棵树的Prufer序列为{3,5,1,3}

这样可以得到一个长度为n-2的序列。很容易证明,树和Prufer序列是一一对应的

Prufer序列显然满足一个性质:一个点若度数为d,则一定在Prufer序列中出现了d-1次

于是这就变成了一个排列组合的问题了

令每个已知度数的节点的度数为di,有n个节点,m个节点未知度数,left=(n-2)-(d1-1)-(d2-1)-...-(dk-1)

已知度数的节点可能的组合方式如下

(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left!

剩余left个位置由未知度数的节点随意填补,方案数为m^left

于是最后有

ans=(n-2)!/(d1-1)!/(d2-1)!/.../(dk-1)!/left! * m^left

答案很显然有高精度,为了避免高精度除法我们可以对每个阶乘暴力分解质因数,对指数进行加减操作即可

代码如下:

n = input()
a = [1 for i in range(n-1)]
num = n - 2
cnt = int(0)
for i in range(n):
x = input()
if x == -1:
cnt += 1
continue
num -= x - 1
for j in range(x):
a[j] -= 1 for i in range(num+1):
a[i] -= 1
ans = int(1)
for i in range(n-2, 0, -1):
if a[i] > 0:
for j in range(a[i]):
ans *= i
else:
for j in range(a[i], 0, 1):
ans /= i
for i in range(num):
ans *= cnt
print ans