上周末做了一套 XVI Open Cup named after E.V. Pankratiev. GP of Asia 的题目，其中有题是这样的：
给你$n$个不同的点，问有多少棵无根树，使得第$i$个节点的标号为$a_i$，有$1\le a_i\le 3$
这一题看榜上的一血是3分钟，不知道为啥毛子的手速都那么快。
最开始想的是DP，因为我们可以把根度为2的结点直接去掉，这样就得到了一棵二叉树，后来越来越感觉不可做。
中途想到了在组合数学上知道的一个叫Purfer的东西，然后只知道长度为$n-2$的这个编码与结点数为$n$的树有一一对应关系，但不知道细节。
结束之后查题解发现了一个叫Cayley公式的东西：
这题的答案是$(n-2)!/\prod (a_i-1)!$
就是说，如果有$n$个有标号的结点，第$i$个结点的度数为$a_i$，那么这$n$个结点可以组成$(n-2)!/\prod(a_i-1)!$棵树。
简单证明一下……
考虑Purfer编码的构造过程，我们发现，度数为$k$的结点在编码中出现了$k-1$次，分别是在删去它的$k-1$个编号比它小的结点的时候出现的。
然后这题就是个公式题，接下来就随便搞搞就可以了，需要注意的是要特判掉不存在这样的树的情况。
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int maxn = 100000 + 5;
long long frac[maxn], ifrac[maxn];
long long pow_mod(long long a, long long b)
{
long long ret = 1;
while (b)
{
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}
int main()
{
int n;
frac[0] = 1;
cin >> n;
for (int i = 1; i <= n; i++) frac[i] = frac[i - 1] * i % mod;
ifrac[0] = 1;
for (int i = 1; i <= n; i++) ifrac[i] = pow_mod(frac[i], mod - 2);
long long ans = frac[n - 2];
int sum = 0;
for (int i = 1; i <= n; i++)
{
int tr = 0;
cin >> tr;
sum += tr;
(ans *= ifrac[tr - 1]) %= mod;
}
cout << (sum == n * 2 - 2) * ans << endl;
return 0;
}