以下、手順 1,2,3 を 1 回行う一連の流れを 1 ターンと表現します。

\(\mathrm{DP}[t][k]\) を「\(t\) ターン目が終わった時点で当たりのボタンが \(k\) 回押された状態からゲームを続け、最適な行動をしたときの勝率」と定め、\(t\) の降順に求めます。

\(\mathrm{DP}[t+1][*]\) から \(\mathrm{DP}[t][k]\) を求める方法を考えます。\(t+1\) ターン目に各 \(i=1,\dots,N\) についてボタン \(i\) を \(c_i\) 回押すとき、どのボタンがあたりであるかはそれぞれ \(\frac{1}{N}\) なので、勝率は \(\frac{1}{N}\sum_{i=1}^{N} \mathrm{DP}[t+1][k+c_i]\) となります。よって、どのボタンを何回押すかを全て考慮することで以下の漸化式を得ます。

\(\displaystyle \mathrm{DP}[t][k]=\max_{c_1+\dots+c_N=M}\frac{1}{N}\sum_{i=1}^{N} \mathrm{DP}[t+1][k+c_i]\)

これを高速に求めることを考えます。\(t,k\) を固定し、

\(\displaystyle \mathrm{DP}'_{t,k}[n][s]=\max_{c_1+\dots+c_n=s}\sum_{i=1}^n \mathrm{DP}[t+1][k+c_i]\)

と定めると定義より \(\mathrm{DP}[t][k]=\frac{1}{N}\mathrm{DP}'_{t,k}[N][M]\) です。\(\mathrm{DP}'_{t,k}[N][M]\) を求めるにあたって、\(c\) の順序は影響しないことから、\((c_i=0 \land i\leq i') \Rightarrow c_{i'}=0\) すなわち「\(c_i=0\) であるような \(i\) は全て後ろに固まっている」というような \(c\) のみを考慮するとしてよいです。これを踏まえ、\(c\) に \(0\) でない要素がいくつあるかを考えることで、

\(\displaystyle \mathrm{DP}''_{t,k}[n][s]=\max_{\substack{c_1+\dots+c_n=s\\ c_i>0}}\sum_{i=1}^n \mathrm{DP}[t+1][k+c_i]\)

と定めると、\(\displaystyle \mathrm{DP}'_{t,k}[N][M]=\max_{1\leq n\leq \min(M,N)} (\mathrm{DP}''_{t,k}[n][M]+(N-n)\mathrm{DP}[t+1][k])\) を得、\(1\leq n \leq \min(M,N)\) の範囲で \(\mathrm{DP}''[n][M]\) が 求まれば \(\mathrm{DP}'_{t,k}[N][M]\) を求めることができます。\(\mathrm{DP}''\) を求める DP は状態数 \(O(M^2)\)、遷移 \(O(M)\) であることから \(O(M^3)\) 時間で行えます。

以上を全ての \(t,k\) に対して行うことで、\(O(TKM^3)\) でこの問題を解くことができました。