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

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

HINT

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

Source

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

把一棵树进行以下操作：

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

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

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

最小叶节点为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