可読性のため、以下 \(p=\frac{1}{2}\) とします。

動的計画法によりこの問題を解きます。

\(\mathrm{dp}[i][j]\) を、今列に \(i\) 人いるときに、先頭から \(j\) 番目の人が最後に残る確率と定義します。求めたいものは \(\mathrm{dp}[N][1],\ldots,\mathrm{dp}[N][N]\) です。

dp テーブルを \(i\) の昇順に埋めましょう。

列に \(i\) 人いるとき、先頭から \(k\) 番目の人が列から取り除かれるとします。このような確率は、現在から \(k\) 回目の操作で初めて人が取り除かれる確率、現在から \(k + i\) 回目の操作で初めて人が取り除かれる確率、現在から \(k +2 i\) 回目の操作で初めて人が取り除かれる確率、\(\ldots\) を足し合わせればよく、

\[p^{k}(1 + p ^ i + p^{2i}+\ldots) = \frac{p^{k}}{1-p^i}\]

と求めることができます。 (ここで無限等比級数の和の公式を用いました）

この式を用いることで、この問題を \(\mathrm{O}(N^3)\) で解くことができますが、高速化が必要です。

遷移の形を具体的に見てみましょう。例えば \(i=4\) のときを貰う DP によって考えると、以下のようになっています。（なお、以下では便利のため 0-indexed で考えています。）(また、各項に共通の係数である \(\frac{p}{1-p^i}\) は省略しています。)

• \(\mathrm{dp}[5][0] = \mathrm{dp}[4][3]p^1 + \mathrm{dp}[4][2] p^2+ \mathrm{dp}[4][1] p^3 + \mathrm{dp}[4][0] p^4 \)

• \(\mathrm{dp}[5][1] = \mathrm{dp}[4][0] p^0+ \mathrm{dp}[4][3] p^2+ \mathrm{dp}[4][2] p^3 + \mathrm{dp}[4][1] p^4 \)

• \(\mathrm{dp}[5][2] = \mathrm{dp}[4][1] p^0+ \mathrm{dp}[4][0] p^1+ \mathrm{dp}[4][3] p^3 + \mathrm{dp}[4][2] p^4 \)

• \(\vdots\)

この遷移の式を眺めると、\(\mathrm{dp}[i+1][j]\) に加算される値と \(\mathrm{dp}[i+1][j+1]\) に加算される値が似た形をしていることが分かります。

実際、\(p^{i}\) の項以外は、\(\mathrm{dp}[i+1][j+1]\) に加算される値が \(\mathrm{dp}[i+1][j]\) に加算される値の \(p\) 倍となっています。

以上より、\(\mathrm{dp}[i+1][j]\) が分かっていれば適当な処理により \(\mathrm{dp}[i+1][j+1]\) の項は \(\mathrm{O}(1)\) で求められます。（実装例も参考にしてください。）

\(\mathrm{dp}[i+1][0]\) は愚直に \(\mathrm{O}(N)\) かけて求めて、\(\mathrm{dp}[i+1][j+1]\) は \(\mathrm{O}(1)\) で求めることで、この問題は \(\mathrm{O}(N^2)\) で解けます。

実装例