ARC174-C Catastrophic Roulette（Difficulty: 1706）の解説です．
問題
先手と後手が交互にルーレット（1 から N までの整数値の目が等確率で出る）を回す．ただし既に出た目が出た場合には罰金 1 円を払う．全ての目がそれぞれ 1 回以上出た時点で終了する．
先手と後手がそれぞれ払う罰金の期待値を求めよ．
制約
- 1\leq N\leq 10^6
解答
出ていない目が i 個ある状態からゲームを始めたときに先手と後手が払う罰金の期待値をそれぞれ A_i, B_i とします．このとき A_i, B_i は，
\begin{aligned}A_i &= \frac iN B_{i-1} + \frac{N-i}N \left(B_i + 1\right)\\B_i &= \frac iN A_{i-1} + \frac{N-i}N A_i\end{aligned}
を満たします．いま，C_i = A_i + B_i, D_i = A_i - B_i とします．上の式の両辺を足すか引くかして，
\begin{aligned}C_i &= \frac iN C_{i-1} + \frac{N-i}N \left(C_i + 1\right)\\D_i &= -\frac iN D_{i-1} - \frac{N-i}N \left(D_i - 1\right)\end{aligned}
を得ます．これを整理すると，
\begin{aligned}C_i &= C_{i-1} + \frac{N-i}i\\D_i &= -\frac i{2N-i}D_{i-1}+\frac{N-i}{2N-i}\end{aligned}となり，C_i たちと D_i たちを独立に i の昇順に求められます．問題の答えは A_N = (C_N+D_N)/2, B_N = (C_N-D_N)/2 です．
計算量は \mathrm{O}(N+\log\mathrm{MOD}) や \mathrm{O}(N\log\mathrm{MOD}) です．