人 \(i\) については最初に \(i-1\) 回操作を行うことで人 \(1\) についての問題に帰着できます。この過程で \(a\) 人減る確率 (\(0 \leq a \leq i - 1\)) は、 \(\displaystyle \frac{\binom{i-1}{a}}{2^{i-1}}\) です。

\(\mathrm{dp}_n\) を、 \(n\) 人から始めたとき人 \(i\) が勝つ確率とします。

\(\mathrm{dp}_1 = 1\) です。また \(n \geq 2\) において \(\displaystyle \mathrm{dp}_n = \sum_{i=1}^{n - 1} \frac{\binom{n-1}{n-i}}{2^n - 1} \mathrm{dp_i}\) です。

先程の帰着から、 人 \(i\) についての答えは \(\displaystyle \sum_{a=0}^{i-1} \frac{\binom{i-1}{a}}{2^{i-1}}\mathrm{dp}_{n - a}\) です。

以上は、適切に逆元を前計算して式の通りに計算すれば、いずれも \(O(n^2)\) で計算できます。