\(f(n, k) :=\) 列に \(n\) 人いるとき、（0-indexed で）先頭から \(k\) 番目の人が最後に残る確率 とします。（この DP 定義は公式解説と同様です）

\(0\) 番目の人が最後に残るためには、最初の操作で取り除かれない必要があります。このときこの人は \(n-1\) 番目に移動するので、

\[f(n, 0) = \frac{1}{2} f(n, n-1) \tag{1}\]

が成立します。

他の人（\(k\) 番目）については、その人が初めて \(0\) 番目に移動するまでに取り除かれる人数 \(j\) で場合分けすることで、

\[f(n, k) = \sum_{j = 0}^k \frac{1}{2^k} \binom{k}{j} f(n-j, 0) \quad (k \neq 0) \tag{2}\]

が得られます。これを愚直に実装すると \(\Theta(N^3)\) の DP になります。

高速化のためにさらに変形します。\((2)\) 式で \(k = n - 1\) としたものと \((1)\) 式を連立することにより

\[f(n, 0) = \frac{1}{2^n - 1} \sum_{j=1}^{n-1} \binom{n-1}{j} f(n-j, 0) \tag{3}\]

が得られます。

\((3)\) を利用することで、\(n = 1, 2, \ldots, N\) に対する \(f(n, 0)\) を \(O(N^2)\) の DP で求めることができます。これが求まれば、\((2)\) から \(k = 0, 1, \ldots, N - 1\) に対する \(f(N, k)\) を \(O(N^2)\) の DP で求めることができます。以上より全体 \(O(N^2)\) で解くことができました。