题目链接
题解
prufer序
可重排列计数
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n = 0;
int b[10007];
int cnt[10007];
void Div(int x,int k = 1) {
for(int j = 2;j * j <= x;++ j) {
while(x % j == 0) {
cnt[j] += k;
x /= j;
}
}
cnt[x] += k;
}
main() {
int tot = 0;
scanf("%lld",&n);
for(int i = 1;i <= n;++ i) {
scanf("%lld",&b[i]);
if(!b[i] && n > 1) {
puts("0");return 0;
}
tot += b[i];
}
if(tot - n != n -2 ) {
puts("0"); return 0;
}
if(n <= 2) {puts("1"); return 0; }
for(int i = 2;i <= n - 2; ++ i) Div(i);
for(int i = 1;i <= n;++ i) {
for(int j = 2;j < b[i];++ j) Div(j,-1);
}
long long ans = 1;
for(int i = 1;i <= n;++ i)
for(int j = 1;j <= cnt[i];++ j) ans *= i;
cout << ans <<endl;
return 0;
}