ケイリーの公式を活用する。
今回の場合、次数 $d_i$ には親に向かう辺がカウントされていないので、$i \neq 1$ の $d_i$ にそれぞれ1を足すと、
無向木の次数に相当するものになる。(が、以下の説明ではとりあえず $d_i$ のままで説明する)
まず、良い木の個数は、ケイリーの公式を使って、以下のようになる。
主客転倒して、各頂点に対して「自身が良い頂点となる良い木の個数」を求め、合計することを考える。
頂点 $1$ と葉は必ず良い頂点なので、良い木の個数だけ存在する。
それ以外の、$i \ge 2, d_i \ge 1$ の頂点について考える。
いま、$v$ の部分木に含まれる頂点集合が $S$ と決まっているとする。
$S$ が $v$ 以上の頂点でのみ構成されていれば、$v$ は良い頂点となれる。
木の頂点数と辺数の関係上、$\displaystyle \sum_{i \in S}d_i = |S|-1$ である必要がある。
$S$ を固定した良い木の個数は、($S$ からできる木の個数) × ($v$ と、$S$ に含まれない頂点からできる木の個数) で
分割して求めることができる。
後者において、$v$ は葉の扱いとなる。
○ ○
/ \ / \
○ ○ = × ○ ○
/ \ | / \ |
○ ⓥ ○ ⓥ ○ ⓥ ○
/\ /\
○○ ○○
※図化のため具体的な木の形状を表現したが、
実際は、それぞれの木での次数条件を満たす全ての個数を考える
両者をケイリーの公式で表すと、
これを整理すると、分母が綺麗な形になる。
つまり、$S$ の具体的な構成要素に依らず、
$v$ が良い頂点になれる良い木の個数は $S$ のサイズが分かれば計算できることになる。
ただし、辺数の制約($\displaystyle \sum_{i \in S}d_i = |S|-1$)は満たす必要があるため、
この2つを状態に持ったDPでパターン数を数える。
遷移の過程で、以下のような $S$ について、先ほどの式で1パターン当たりの木の個数を求め、答えに加算していけばよい。
$O(N^3)$ で求められる。
Python3
import numpy as np
def precompute_factorials(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f = f * m % MOD
factorials.append(f)
f = pow(f, MOD - 2, MOD)
finvs = [1] * (n + 1)
finvs[n] = f
for m in range(n, 1, -1):
f = f * m % MOD
finvs[m - 1] = f
return factorials, finvs
n = int(input())
ddd = list(map(int, input().split()))
MOD = 998244353
zero_count = 0
facts, finvs = precompute_factorials(n, MOD)
all_prod = facts[ddd[0] - 1]
for i in range(1, n):
if ddd[i] > 0:
all_prod = all_prod * facts[ddd[i]] % MOD
else:
zero_count += 1
all_prod_inv = pow(all_prod, MOD - 2, MOD)
# 葉頂点+根は必ず良い頂点
ans = facts[n - 2] * (zero_count + 1) % MOD
dp = np.zeros((n, n), dtype=np.int64)
dp[0, 0] = 1
for i in range(n - 1):
d = ddd[-i - 1]
if d > 0:
for j in range(d, i + 1):
if dp[j, j - d] > 0:
tmp = dp[j, j - d] * d % MOD
tmp *= facts[j - 1]
tmp %= MOD
tmp *= facts[n - j - 2]
tmp %= MOD
ans += tmp
ans %= MOD
dp[1:, d:] += dp[:-1, :-d]
else:
dp[1:, :] += dp[:-1, :]
dp %= MOD
ans *= all_prod_inv
ans %= MOD
print(ans)