FPS24 E - 数列 3

考え方

何を何個使うかのパターン数だけ数えればよいのなら、以下の全ての積の $x^N$ の係数でよい。

• $A_1(x) = 1+x$
• $A_2(x) = 1+x+x^2$
• $A_3(x) = 1+x+x^2+x^3$
• $A_4(x) = 1+x+x^2+x^3+x^4$
• 中略
• $A_M(x) = 1+x+x^2+x^3+x^4+\dots+x^M$

しかし、今回はその後に並べ替えをしなければならない。
つまり、$1$ が $n_1$ 個、$2$ が $n_2$ 個、……、$M$ が $n_M$ 個あるなら、$\dfrac{N!}{n_1!n_2!\dots n_M!}$ 倍する必要がある。

この「各指数の合計の階乗をかけ、各指数の階乗の積で割る形」は、指数型母関数の出番。
詳しくは「形式的冪級数」の記事参照。

ということで、母関数は以下のようにとる。

• $A_1(x) = 1+x$
• $A_2(x) = 1+x+\dfrac{x^2}{2}$
• $A_3(x) = 1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}$
• $A_4(x) = 1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\dfrac{x^4}{24}$
• 中略
• $A_M(x) = 1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\dfrac{x^4}{24}+\dots+\dfrac{x^M}{M!}$

これら全ての積の $\dfrac{x^N}{N!}$ の係数でよい。
畳み込んだ結果の係数は $x^N$ の係数として出てくる。
つまりこの分母の $N!$ の分までふくまれてしまっているので、$N!$ をかけてから答える。

$1$ 回畳み込むごとに、$x^{N+1}$ 以降は切り落とす前提で、計算量を考える。
愚直な畳み込みで毎回 $O(MN)$ かかっても、全体 $O(M^2N)$ で今回の制約下なら間に合う。
NTTで毎回 $O((M+N)\log (M+N))$ で済むなら $O(M(M+N)\log (M+N))$ で求められる。

入力例1での動作

入力を受け取る。

n: 2
m: 3

最初は $f(x)=1$ とする。
$A_1(x)=1+x$ を掛けると、$f(x)=1+x$ となる。

次に $A_2(x)=1+x+\dfrac{x^2}{2}$ を掛け、$x^2$ まで残す。
$$
f(x)=1+2x+\dfrac{3}{2}x^2
$$

さらに $A_3(x)=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}$ を掛け、同様に $x^2$ まで残す。
$$
f(x)=1+3x+4x^2
$$

$x^2$ の係数は $4$ なので、これに $2!=2$ を掛ける。
よって、答えは $4\times 2=8$ となる。

注意点

階乗の逆数は $998244353$ 上の逆元を用いて求める。
逆元は繰り返し二乗法で求める。

別解

特になし。