洛谷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