メイダイ君が条件に従って行動したとき、体力が \(h\) で家が \(k\) 個作られた状態になる確率を \(P_{h, k}\) とします。 最初、メイダイ君の体力は \(H\) であり、家を \(K\) 個作った時点で行動をやめることに注意すると、 \(P_{h, k}\) は次の関係式を満たします。

\[ P_{h,k} = \begin{cases} \frac{h+1}{H}P_{h+1, k-1} + \frac{H-h+1}{H}P_{h-1, k} &(0 < h < H, 0 < k < K) \\ \frac{H-h+1}{H}P_{h-1, k} &(h = H, 0 < k < K) \\ \frac{h+1}{H}P_{h+1, k-1} &(h = 0 \text{ or } k = K) \\ \end{cases} \\ \]

\[ P_{h, 0} = 0 \quad (0 < h < H) \]

\[ P_{H, 0} = 1 \]

よって、 \(P_{h, k}\) はDPで求めることができます。モジュラ逆数を事前に計算しておくことで、各計算を \(O(1)\) で行うことができます。

最後に期待値を求めます。家の個数が \(K\) になったとき、それまでに消費した木の本数（合計の行動回数）は、そのときの体力 \(h\) に対して、 \(h-H+2K\) で一意に定まります。つまり、 \(K\) 個の家を作って、最後の体力が \(h\) となるときの消費した木の本数の期待値は、 \(P_{h, K} \times (h-H+2K)\) です。よって、求める答えは \(\sum_{h=0}^{H}{P_{h, K} \times (h-H+2K)}\) です。

行動回数が一意に定まることの証明

メイダイ君の行動終了時（家が \(K\) 個できた時点）の状態を考えます。このとき、初期体力を \(H\)、最終的な体力を \(h\)、食べた木の本数（行動 \(2\) を行った回数）を \(x\) とします。体力の増減を考えると、家を \(K\) 個作ることで体力が \(K\) 減少し、 \(x\) 本の木を食べることで体力が \(x\) 増加するため、 \(h = H - K + x\) が成り立ちます。この式を \(x\) について解くと、休憩した回数は \(x = h - H + K\) となります。合計の消費本数は、 \(x + K = (h - H + K) + K = h - H + 2K\) となります。これにより、行動終了時の体力 \(h\) と作った家の数 \(K\) から、合計の消費本数が一意に定まることが示されました。

計算の際は、オーバーフローと期待値を \(\mod 998244353\) で答えることに注意してください。

計算量は \(O(HK)\) で、これは十分高速です。

クレジット

原案： hamao

解法： hamao, mono_1729, null0124

問題準備・解説： hamao

レビュー： S0ni, nu50218

テスター： tatyam

校正： nu50218