ARC154-F Dice Gameの立式パート～何にでも積の和典型を注ぐ女子高生～

ARC154-F Dice Gameの立式を積の和典型でやりまふ. maspyしゃんの解説に出てくるモーメント母関数を用いた議論と本質的に同じ話という気はしまふが, モーメント母関数よりも積の和典型に慣れている人が多いと思われること, 及び積の和典型をこの問題に使っても良いという言及のためにこのような解説をすることにしまふ.

元問題におけるサイコロを振る回数の $K$ 乗を求める問題は以下のように書き換えられまふ.

$K$ 個の区別するボールを用意し, サイコロを振る度に $0$ 個以上選んで食べる. 最後までに $K$ 個食べる方法の個数の期待値は？(ボールを食べる方法は, あるサイコロを振った時において食べたボールの集合が異なる場合に区別する)

「 $\mathrm{dp}_{i,j}$ ： $i$ 種類の目が出るまでに合計 $j$ 個ボールを食べる方法の個数の期待値(ただしここではボールの区別の扱いを変える)」としまふ. 一旦簡単のために新しい目が確率 $1$ で出るものとして考えると, $x$ 個食べる場合には通り数について $\frac{1}{x!}$ を係数とする遷移を行って, $\mathrm{dp}_{N,K}$ に $K!$ を掛けることで求められまふ. (類題 ECR78-F, PG BATTLE 2022 せんべい難易度6)*1

これを高速化するにあたり, 上記 $\mathrm{dp}$ テーブルの添え字 $j$ を $x$ の指数, 値を係数とするFPSを考えまふ. ここで, 前述の通り数についての係数は $\sum_{i=0}^{\infty}{\frac{x^i}{i!}} = e^x$ となるので以降このように表記しまふ.

確率についての係数を考えまふ. $i=0,1,\ldots,N-1$ に対し出た目の種類数が $i$ から $i+1$ になる時に $y$ 回サイコロを振ることになる確率は $\frac{N-i}{N} (\frac{i}{N})^y$ れふ. これに先の通り数についての係数を掛けると, 遷移を表すFPSは $\sum_{y=0}^{\infty}{\frac{N-i}{N} e^x (\frac{i}{N} e^x)^y}$ になりまふ. $\sum_{i=0}^{\infty}f^i = \frac{1}{1-f}$ より, この式は $\frac{(N-i)e^x}{N-ie^x}$ となりまふ. このため, 求めるべきは $\prod_{i=0}^{N-1} \frac{(N-i)e^x}{N-ie^x}$ となり, 立式が完了しまふ.

*1:積の和典型パートはここまでではある