洛谷P2290 [HNOI2004]树的计数 题解

题目链接：P2290 [HNOI2004]树的计数

题意：

一个有 $n$ 个节点的树，设它的节点分别为 $v_1,v_2,\ldots,v_n$，已知第 $i$ 个节点 $v_i$ 的度数为 $d_i$，问满足这样的条件的不同的树有多少棵。

输入格式：

输入文件第一行是一个正整数 $n$ ，表示树有 $n$ 个结点。第二行有 $n$ 个数，第 $i$ 个数表示 $d_i$，即树的第 $i$ 个结点的度数。

输出格式：

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

数据范围：

$1\le n\le 150$，保证满足条件的树不超过 $10^{17}$ 个。

Prüfer 序列简单题。详见浅谈 Prüfer 序列

则对于给定度数 $d_{1\sim n}$ 的一棵无根树一共有 $\dbinom{n-2}{d_1,d_2,\cdots,d_k}=\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}$ 种情况。

本题需要高精度。因此我使用 $\mathtt{Python}$

时间复杂度 $O(n\times c)$ ，$c$ 为数字位数产生的常数

代码：

n = int(input())
if n == 1: # 特判n=1的情况
    x = int(input())
    if(x == 0): print(1)
    else: print(0)
    exit()

fac = [0 for i in range(n+5)]; fac[0] = 1 # 预处理阶乘
for i in range(1,n+1): fac[i] = fac[i-1] * i
ans = fac[n-2]; tot=0; s=input().split()
for i in range(n):
    x = int(s[i])
    if(x == 0): print(0); exit() # 图不连通。
    tot += x-1; ans //= fac[x-1]
if(tot == n-2): print(ans)
else: print(0)

参考文献：

[1] https://www.luogu.com.cn/blog/TheLostWeak/solution-p2290