問題リンク

atcoder.jp

問題概要

$N$ 個の部品があって、 $i$ 番目の部品には $d_i$ 個の穴があるよ。これらの穴は区別できるよ。

また、 $N-1$ 個の接続用部品があるよ。

これらを連結になるようにつなげる通り数を $998244353$ で割ったあまりを求めてね。

解法

まずは、次数制限つきケイリーの定理を考えます。

これは頂点 $i$ の次数が $a_i$ である $N$ 頂点のラベル付き木*2の個数が $\frac{(N-2)!}{(a_1-1)!(a_2-1)!\dots(a_i-1)!}$ であるというものです。*3

また、部品 $i$ に刺す部品の個数が $a_i$ のとき、通り数は $_{d_i}\text{P}_{a_i}$ です。

なので、答えは

$\sum_{a_1+a_2+\dots+a_N=2N-2}\frac{(N-2)!{_{d_1}\text{P}_{a_1}}{_{d_2}\text{P}_{a_2}}\dots{_{d_N}\text{P}_{a_N}}}{(a_1-1)!(a_2-1)!\dots(a_i-1)!}$

となります。

とりあえず $(N-2)!$ は最後に掛けることにすると、答えは

$(N-2)!\sum_{a_1+a_2+\dots+a_N=2N-2}\frac{_{d_1}\text{P}_{a_1}}{(a_1-1)!}\frac{_{d_2}\text{P}_{a_2}}{(a_2-1)!}\dots\frac{_{d_N}\text{P}_{a_N}}{(a_N-1)!}$

となります。

ここで、それぞれの項を見てみましょう。 $\frac{_{d_i}\text{P}_{a_i}}{(a_i-1)!}$ はほぼ二項係数です。もっと言うと、これは $d_i\times{_{d_i-1}\text{C}_{a_i-1}}$ です。

すると、さらに

$(N-2)!d_1d_2\dots d_N\sum_{a_1+a_2+\dots+a_N=2N-2}{_{d_1-1}\text{C}_{a_1-1}}{_{d_2-1}\text{C}_{a_2-1}}\dots{_{d_N-1}\text{C}_{a_N-1}}$

と変形できます。

左はめちゃくちゃ簡単なので、右の二項係数たちを考えます。すると、それぞれは二項定理を取り出して $[x^{a_i-1}](1+x)^{d_i-1}$ と表せます。

また、この総和は明らかに畳み込みです。そのため、さらに

$(N-2)!d_1d_2\dots d_N[x^{N-2}](1+x)^{\sum_{i=0}^{N} d_i-1}$

と変形できます。この右にも二項定理を適用できるので、最終的には

$(N-2)!d_1d_2\dots d_N{_{\sum_{i=0}^{N} d_i-1}\text{C}_{N-2}}$

となります。このまま計算することも可能ですが、

$(N-2)!d_1d_2\dots d_N{\frac{_{\sum_{i=0}^{N} d_i-1}\text{P}_{N-2}}{(N-2)!}}$

と解釈すれば

$d_1d_2\dots d_N{_{\sum_{i=0}^{N} d_i-1}\text{P}_{N-2}}$

とできて、もう掛け算をやるだけです。

提出コード

MOD=998244353
N=int(input())
d=list(map(int,input().split()))
top=1
for i in range(N-2):
    top*=(i+1)
    top%=MOD
mul=1
for i in d:
    mul*=i
    mul%=MOD
comb=1
n=sum(d)-N
for i in range(N-2):
    comb*=(n-i)
    comb%=MOD
print(comb*mul%MOD)