概要

公式解説では，ゲームの開始時点からある時点までの情報を $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$ 項の計算に使うことができます．