概要

公式解説では，ゲームの開始時点からある時点までの情報を \(4\) 変数で表すことで dp をしていました．

ある時点からゲームの終状態までの情報を考えると， \(2\) 変数での dp の立式ができます．また，適切に立式すれば，無限和の類を考えずに解くことができます（この手の期待値の計算で頻出のテクニックです）．

解法

まだ出ていない数の種類が \(n\) である状態（以下「状態 \(n\)」）で先手番から始めたときの，先手番の罰金期待値を \(F_n\)，後手番の罰金期待値を \(S_n\) とします．

\(p = n/N\), \(q=1-p\) とします（それぞれ未出の数・既出の数が出る確率です）．

この状態での先手番は，

• はじめに未出の数が出たら，次からは状態 \(n-1\) での後手番をプレイするとみなせる．
• はじめに既出の数が出たら，罰金 \(1\) を払ったあと，次からは状態 \(n\) での後手番をプレイすると見なせる．

ことから，\(F_n = pS_{n-1}+q(1+S_n)\) という立式ができます．同様に，\(S_n = pF_{n-1} + qF_n\) という立式ができます．

\(F_{n-1}, S_{n-1}\) を既知とすれば，これら \(2\) つの式は \(F_n, S_n\) を未知数とする連立 \(1\) 次方程式となり，これを解くことで \(F_n, S_n\) が計算できます．\(n=0\) の場合に \(F_n=S_n=0\) であるところからはじめて \(n=1, 2, \ldots, N\) の順に計算していけばよいです．

• 解答例：https://atcoder.jp/contests/arc174/submissions/51367897

\(1-q^2\) による除算があり，この解答例の時間計算量は \(O(N\log(\mathrm{mod}))\) です．なお，\(1-q^2=\frac{n(2N-n)}{N^2}\) 等から \(2N\) 以下の整数による除算だけが必要なので，時間計算量を \(O(N)\) にすることも可能です．

参考

漸化式は \(n\) に関する多項式行列 \(M(n)\) をかけるという形で表せるので，\(\{F_n\}\) や \(\{S_n\}\) の計算は行列積 \(M(1)\cdots M(N)\) の計算という形の問題に帰着できます．このような計算は \(O(\sqrt{N}\log N)\) 時間で行えることが知られており，本問の \(F_N, S_N\) を含む P-recursive な数列の第 \(N\) 項の計算に使うことができます．