本番全くわからなくて焦った…

解説読んでもあんまりピンと来なかったのですが、半日考え直してようやく理解できたので記事にします。

解法

無限に誰も排除されないことがあるけどどうしよう...となるので、とりあえずサンプル1がなんでこれでいいのかを解き明かさないといけない。

まず1周目で1人目が排除される確率は $\frac{1}{2}$ 、2人目が排除される確率が $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$ 、2周目に回って、1人目排除が $\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{8}$ ．．．と続き、それぞれの総和がそれぞれの排除される確率であることがわかる。

もうちょっと考えると、1人目が排除される確率は $\frac{1}{2}(1+\frac{1}{4}+\frac{1}{16}...)$ となって、2人目が排除される確率は $\frac{1}{4}(1+\frac{1}{4}+\frac{1}{16}...)$ となることもわかる。

ここまでくると、 $x = \frac{1}{4}$ として、 $1 + x + x^{2} + x^{3} + x^{4} + ...$ みたいなものを計算したくなってくる。
$1 + x + x^{2} + .... + x^{n} = \frac{1-x^{n+1}}{1-x}$ であって $x = \frac{1}{4}$ なので、雑に考えると $n$ を無限に飛ばせば $x^{n+1}$ は $0$ になって消えるでしょう、みたいな気持ちになると、上の式は $\frac{1}{1-x}$ と等しいだろうと予想できる。
実際色々ググってみたりするとこれが正しいことはわかる。

これをもとにサンプル1の話に戻ると、1人目が排除される確率は $\frac{1}{2}\cdot\frac{4}{3}=\frac{2}{3}$ 、2人目が排除される確率は $\frac{1}{4}\cdot\frac{4}{3}=\frac{1}{3}$ となり、それぞれを1から引けば他方が最後まで残る確率がわかるので、出力が正しいということがわかる。

もう少し抽象化して考えて、 $i$ 人いる状態で、先頭から $j$ 人目（ $0 \le j \lt i$ 、以降単に $j$ と呼ぶ）が排除される確率はいくらだろうということを考えてみる。

1周目で排除される確率は、 $j$ より前が全員 $\frac{1}{2}$ の確率で生き延び、 $j$ が $\frac{1}{2}$ の確率で排除されるため、 $\frac{1}{2^{j+1}}$ となる（ $j$ が0から始まることに注意）。
1周を誰も排除されず周り切る確率は明らかに $\frac{1}{2^{i}}$ なので、2周目以降 $j$ が排除される確率は、 $\frac{1}{2^{i+j+1}}, \frac{1}{2^{2i+j+1}}, \frac{1}{2^{3i+j+1}}...$ となり、これらの総和が $j$ が排除される確率になる。

これを式にすると、

$\sum^{\infty} _ {k=0} {\frac{1}{2^{ki+j+1}}}$

となり、整理すると、

$\begin{eqnarray} \sum ^ {\infty} _ {k=0} {\frac{1}{2^{ki+j+1}}} &=& \frac{1}{2^{j+1}} \sum ^ {\infty} _ {k=0} {\frac{1}{2^{ki}}} \\\\ &=& \frac{1}{2^{j+1}} \sum ^ {\infty} _ {k=0} {(\frac{1}{2^{i}}) ^ {k}} \\\\ &=& \frac{1}{2^{j+1}} \cdot \frac{1}{1 - \frac{1}{2^{i}}} \\\\ &=& \frac{1}{2^{j+1}} \cdot \frac{2^{i}}{2^{i} - 1} \\\\ &=& \frac{2^{i-j-1}}{2^{i} - 1} \end{eqnarray}$

となることがわかる。長いので、以降はこの式を $p _ {i, j}$ と表すことにする。

（ここまではコンテスト中に分かっていた点で、以降はコンテスト後の考察）

これを使って、以下のようなDPを考える。

$dp _ {i, j} := i$ 人残っている時点で $j$ 人目であるような人が最後まで生き残る確率

まず、1人しか残っていない時点で0番目であるような人が生き残る確率は $1$ なので、 $dp _ {1, 0} = 1$ とわかる。

これを昇順に計算することを考えるが、遷移の考え方がちょっとこんがらがる。
たとえば、 $i$ 人いる状態で $j$ 人目だった人が、 $i-1$ 人いる状態で $0$ 人目になるにはどういう遷移をするか考えると、これは $j - 1$ 人目が排除されたときなので、

$dp _ {i, j} += dp _ {i-1, 0} p _ {i, j-1}$

と遷移できる。同じように $1$ 人目、 $2$ 人目...と遷移することを考えると、遷移式は以下のようになる。

$\begin{eqnarray} dp _ {i, j} = &&dp _ {i-1, 0}p _ {i, j-1} + dp _ {i-1, 1}p _ {i, j-2} + dp _ {i-1, 2}p _ {i, j-3} + ... \\\\ &+& dp _ {i-1, j-1}p _ {i, 0} + dp _ {i-1, j}p _ {i, i-1} + dp _ {i-1, j+1}p _ {i, i-2} + ... \\\\ &+& dp _ {i-1, i-2}p _ {i, j+1} \end{eqnarray}$

右辺のそれぞれの項の $dp$ の2つ目の添え字が「 $j$ が生き残った $i-1$ 人の中で何人目になるか」、 $p$ が「 $j$ がそこに移動するためにしかるべき人が排除される確率」であると考えると理解しやすい。

ここまでで $O(N ^ 3)$ 解となるが、これを高速化するには、累積和を用いることができる。

具体的には、 $dp _ {i-1, *}$ の前後から、適切に $p$ をかけて累積和をとる。先頭 $j$ 項は前からの累積和を単に足すだけで良い。以降の $i - j$ 項は後ろからの累積和を用いるが、 $j$ の値は動き続けるので、少し工夫が必要。
$p _ {i, j} = \frac{2^{i-j-1}}{2^{i} - 1}$ を思い出すと、 $j$ が増えるたびに分母の次数が1つずつ下がっていくことがわかる。したがって、 $p _ {i, j}$ から $p _ {i, j+1}$ を導くのは $\frac{1}{2}$ をかければよく、 $p _ {i, j + k}$ は $(\frac{1}{2}) ^ k$ をかけて導けるから、累積和に適切な回数 $\frac{1}{2}$ をかければよい。