模拟赛题。
Prufer 序列做法需要较强的组合数学功底,这里不作解释。
由于除根节点外每个点只有一个父亲节点,考虑从这里入手。
给每个点指定一个特殊点,让这个特殊点连向它的父亲节点的非特殊点。此时只有根节点没有特殊点,可随便指定一个特殊点,因为是无根树,且根节点最后是会与某个节点留下来的。指定特殊点的方案数易知:\(\prod \limits_{i = 1}^{n} d_i\)。
令 \(S = \sum d_i\),因为每个点是由特殊点连向非特殊点,又不能重复经过点,故需再乘上 \(\prod \limits_{i = 0}^{n - 3}(S - n - i)\)。
所以最后的答案为 \(\prod d_i \times\prod(S - n - i)\)。
时间复杂度线性。
代码:
const int N = 2e5 + 10;
int n;
int d[N];
int main () {
ios
cin >> n;
for (int i = 1; i <= n; i++) cin >> d[i];
int sum = 0, ans = 1;
for (int i = 1; i <= n; i++) sum = (sum + d[i]) % mod, ans = 1ll * ans * d[i] % mod;
for (int i = sum - n * 2 + 3; i <= sum - n; i++) ans = 1ll * ans * (i + mod) % mod;
cout << ans << "\n";
return 0;
}