题意分析
对于这种关于树上度数的计数问题，一般会考虑使用 Prüfer 序列求解（Prüfer 序列参见此处）。
Prüfer 序列（Prufer 序列）的主要作用就是将无根树与序列相互转换，每一个确定的无根树都对应一个确定的 Prüfer 序列。
那么对于这道题目，假如树确定了，那么对应的 Prüfer 序列。因此满足条件的树的棵数即 Prüfer 序列的数量。
由 Prüfer 序列的性质：
- Prüfer 长度为 $n-2$。
- 设非叶节点 $i$ 的度数为 $d_i$，则 $i$ 在序列中出现次数为 $d_i-1$。
如果不考虑重复的 Prüfer 序列，则总数量即对于 $n-2$ 个元素进行全排列，即 $(n-2)!$。
但是由于 Prüfer 序列中会有重复的元素，因此要去除一些序列。重复的次数即 $\prod\limits_{i=1}^n(d_i-1)!$。因为每一个重复节点出现之后，交换这些重复节点是没有影响的。单个节点 $i$ 的重复数量是 $(d_i-1)!$，乘起来即可。
故，答案为： \(\dfrac{(n-2)!}{\prod\limits_{i=1}^n(d_i-1)!}\)
小技巧
可以发现，这个题目不需要取模。
这也就意味着，无法再预处理阶乘快速计算。
有一种方法是将 $1\sim n-2$ 放入数组存起来，每次除 $(d_i-1)!$ 时就 $1\sim d_i-1$ 找到其倍数暴力除。最后再将数组中剩余的数乘起来即可。
但是有没有更好的方法呢？
肯定是有的。因为答案不超过 $10^{17}$，因此我们可以找一个大于 $10^{17}$ 的质数 $P$ 作为模数；但是这样对于答案没有任何影响。
而有了 $P$，我们也就可以预处理阶乘、逆元了，从而可以快速计算。
寻找 $P$ 的话，可以写 Miller-Rabin 素性判断，但是没必要。可以直接写 $\mathcal O\left(\sqrt n\right)$ 的质数判断，因为在 $10^{18}$ 附近就有一个质数 $10^{18}+3$。（事实上，$10^{17}+3$ 也是的，但是我想从 $10^{18}$ 开始找）
对于这种常用特殊质数，个人建议还是背一点比较好。（比如 $10^9+7,10^9+9,998244353$）
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef __int128 lll;
typedef long long ll;
constexpr const ll N=150,P=1000000000000000003ll;
int n,d[N+1];
ll fact[N+1];
template<typename T>
T qpow(T base,T n){
T ans=1;
while(n){
if(n&1){
ans=(lll)ans*base%P;
}
base=(lll)base*base%P;
n>>=1;
}
return ans;
}
ll C(int n,int m){
if(n<0||m<0||n<m){
return 0;
}
return (__int128)fact[n]*qpow((lll)fact[n]*fact[n-m]%P,(lll)P-2)%P;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
fact[0]=1;
for(int i=1;i<=N;i++){
fact[i]=(__int128)i*fact[i-1]%P;
}
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
cin>>d[i];
sum+=d[i];
}
if(sum!=2*n-2){
cout<<0<<'\n';
return 0;
}
if(n==1){
cout<<!d[1]<<'\n';
return 0;
}
ll ans=fact[n-2];
for(int i=1;i<=n;i++){
ans=(__int128)ans*qpow(fact[d[i]-1],P-2)%P;
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
