prufer编码
(prufer)序列可以将一个代标号的(n)个节点的树用([1，n])中的(n-2)个整数表示，可以理解为完全图的生成树与数列之间的双射。
出自OI Wiki
有关无根树转(prufer)编码，(prufer)编码转无根树等内容可以去(OI Wiki)上看
这里只介绍(prufer)序列的性质：
-
(prufer)序列与无根树一一对应
相信看完了上面的链接以后您已经懂了。
-
度数为(d_i)的节点会在(prufer)序列中出现(d_i-1)次
根据构造方法，当某个点度数为(1)时会被删掉，否则每次删掉一个相邻节点，它就会入列一次。
-
一个(n)个节点的完全图的生成树个数为(n^{n-2})
对于一个有(n)个节点无根树，它的(prufer)序列长为(n-2)，而每个位置有(n)种可能性，所以共有(n^{n-2})种情况。
-
对于度数为(d_{1-n})的一颗无根树共有(frac{(n-2)!}{prod_{i=1}^{n}{(d_i - 1)!}})种情况
由性质2，度数为(d_i)的节点会在(prufer)序列中出现(d_i-1)次。所以就是(n-2)个位置选出(d_i-1)（(1leq ileq n)）的可重全排列了。
可重全排列/选排列公式：
- 可重全排列：在(n)个元素中，有(n_1)个元素彼此相同，有(n_2)个元素彼此相同……又有(n_m)个元素彼此相同，且(n_1+n_2+cdotcdotcdot+n_m=n)，则这(n)个元素的全排列就是可重全排列。其公式为：(n!/(n_1! imes n_2! imes cdotcdotcdot imes n_m!))。
- 可重选排列：仍是上面拿个序列，从中选出(r)个的选排列就是可重选排列。其公式为：(A(n,r)/(n_1! imes n_2! imes cdotcdotcdot imes n_m!))。
然后就可以愉快地做题了！
模板题Luogu2290
利用最后一个性质即可，注意不要运算过程中爆(long;long)，还有记得判无解。
细节还是蛮多的……
参考代码
/*
* @Author: When_C
* @Date: 2020-11-18 19:01:40
* @Last Modified by: When_C
* @Last Modified time: 2020-11-18 19:29:58
*/
#include <cstdio>
#define LL long long
using namespace std;
const int maxn = 210;
LL n,d[maxn],Ans,f,sum;
LL gcd(LL x, LL y){
if(!y) return x;
return gcd(y, x % y);
}
int main(){
scanf("%lld", &n);
for(int i = 1; i <= n; ++ i) scanf("%lld", &d[i]);
if(n == 1 && d[1] == 0) return printf("1
"), 0; //注意这个特判！！！
Ans = f = 1; int now = 1;
for(int i = 1; i <= n; ++ i){
if(!d[i]) return printf("0
"), 0;
sum += d[i] - 1;
for(int j = 2; j <= d[i] - 1; ++ j){
f *= j;
while(Ans < f && now < n - 2) Ans *= (++now);
LL val = gcd(Ans, f);
Ans /= val; f /= val;
}
}
if(sum != n - 2) return printf("0
"), 0;
while(now < n - 2){
Ans *= (++now);
if(Ans % f == 0 && f != -1) Ans /= f, f = -1;
}
if(f != -1) Ans /= f;
printf("%lld
", Ans);
return 0;
}