晚自习的时候胡出来的做法(((
首先你会发现题目等价于求 \(\sum\limits_{(\sum\limits_{i=1}^n a_i) = 2(n-1) \land \forall i \in [1,n], 1 \le a_i \le d_i} \prod\limits_{i=1}^n \dfrac{d_i!}{(d_i - a_i)!}\)。翻译一下就是枚举每个点的度数 \(a_i\)(一个结论是当度数总和 \(= 2(n-1)\) 并且每个点的度数都为正整数时一定能构造出合法的树),然后乘上对应的有序选择点内的洞的方案。
你会发现如果固定 \(a_i\),这个东西的组合意义是把 \(\sum\limits_{i=1}^n d_i\) 个数分成 \(n\) 组每组 \(d_i\) 个数,再在每组有序选出 \(a_i\) 个数。\(a_i \ge 1\) 比较烦,不妨整体减 \(1\),也就是一开始每组先选一个数,这样就变成了 \(a_i \ge 0\)。然后就发现可以把组合并起来考虑,即答案为先在每组中选一个数再在 \(\sum\limits_{i=1}^n (d_i - 1)\) 个数内有序选择 \(\sum\limits_{i=1}^n (a_i - 1) = n - 2\) 个数的方案数,即 \((\prod\limits_{i=1}^n d_i) \dfrac{(\sum\limits_{i=1}^n (d_i - 1))!}{(n-2)!}\),这个东西可以 \(O(n)\) 计算。
code
// Problem: F - Figures
// Contest: AtCoder - AtCoder Regular Contest 106
// URL: https://atcoder.jp/contests/arc106/tasks/arc106_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
ll n, a[maxn];
void solve() {
scanf("%lld", &n);
ll s = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
s += a[i];
}
if (s < (n - 1) * 2) {
puts("0");
return;
}
s -= n;
ll ans = 1;
for (int i = 1; i <= n; ++i) {
ans = ans * a[i] % mod;
}
for (int i = 0; i < n - 2; ++i) {
ans = ans * ((s - i) % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}