For readability, we denote \(p=\frac{1}{2}\).

We do a dynamic programming (DP) to solve this problem.

Let \(\mathrm{dp}[i][j]\) be the probability that, when there are \(i\) people in the line, the \(j\)-th person from the front is the last person remaining in the line. What we want is \(\mathrm{dp}[N][1],\ldots,\mathrm{dp}[N][N]\),

Let us fill the DP table in ascending order o \(i\).

When there are \(i\) people in the line, consider the case where the \(k\)-th person from the front is the next person to be removed. The probability of such an event is the sum of the probability that a removal occurs for the first time at the \(k\)-th next operation, \((k+i)\)-th operation, \((k+2i)\)-th operation, \(\ldots\); namely

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

(Here, we applied the formula of sum of infinite geometric series.)

This expression allows us to solve this problem in a total of \(\mathrm{O}(N^3)\) time, but we need to optimize it.

Take a closer look at the expression of transition. For example, the receiving DP for \(i=4\) looks like the following. (For convenience, we adopt 0-based indexing here.) (Also, the common coefficient \(1/2^i\) is omitted.)

• \(\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\)

If we stare at this formula, it turns out that the value added to \(\mathrm{dp}[i+1][j]\) and the one to \(\mathrm{dp}[i+1][j+1]\) has a similar form.

Indeed, except for the term for \(p^{i}\), the value added to \(\mathrm{dp}[i+1][j+1]\) is \(p\) times the value added to \(\mathrm{dp}[i+1][j]\).

Thus, if we know \(\mathrm{dp}[i+1][j]\), we can find the \(\mathrm{dp}[i+1][j+1]\) term in \(\mathrm{O}(1)\) time. (See also the sample code.)

By naively evaluating \(\mathrm{dp}[i+1][0]\) spending \(\mathrm{O}(N)\) time, and evaluating \(\mathrm{dp}[i+1][j+1]\) in \(\mathrm{O}(1)\) time, the problem can be solved in a total of \(\mathrm{O}(N^2)\) time.

Sample code