以下の DP を考えます：

• \(dp_1[i][k] :=\) \((i - 1)\) 回操作したときの \(k\) の個数の期待値
• \(dp_2[i][k] :=\) \((i - 1)\) 回操作したときの \(k\) が最大値となる確率

初期値は \(dp_1[1][1] = dp_2[1][1] = 1\) で，それ以外が \(0\) です．

\(dp_1[i + 1][k]\) への遷移を考えます． まず，操作に関わらず \(dp_1[i][k]\) が足されます． 操作 1 については，\((i - 1)\) 回操作したときに \((k - 1)\) が最大値ならば \(dp_1[i + 1][k]\) に寄与します． 操作 2 については，\(k\) が \(dp_1[i][k] / i\) の確率で選ばれると考えてよいです． よって，\(dp_1[i + 1][k] = dp_1[i][k] + p\times dp_2[i][k - 1] + \frac{1 - p}{i}\times dp_1[i][k]\) です．

\(dp_2[i + 1][k]\) への遷移を考えます． 操作 1 については，最大値が 1 増えるので \(dp_2[i][k - 1]\) が寄与します． 操作 2 については，最大値は変化しないので \(dp_2[i][k]\) が寄与します． よって，\(dp_2[i + 1][k] = p\times dp_2[i][k - 1] + (1 - p)\times dp_2[i][k]\) です．

これらを多項式を用いて整理してみます：

• \([x ^ k]P_i(x) = dp_1[i][k]\)
• \([x ^ k]Q_i(x) = dp_2[i][k]\)
• \(P_1(x) = Q_1(x) = x\)
• \(P_{i + 1}(x) = P_i(x) + p\times x Q_i(x) + \frac{1 - p}{i}\times P_i(x)\)
• \(Q_{i + 1}(x) = p\times x Q_i(x) + (1 - p)\times Q_i(x)\)

ところで，下の 2 つの式は \(\begin{pmatrix} P_{i + 1}(x) \\ Q_{i + 1}(x) \\ \end{pmatrix} = \begin{pmatrix} \frac{i + 1 - p}{i} & px \\ 0 & px + 1 -p \\ \end{pmatrix} \begin{pmatrix} P_{i}(x) \\ Q_{i}(x) \\ \end{pmatrix}\) と書き直すことができます． 結局，\(N - 1\) 個の \(2\times 2\) 行列の積を計算できればよく，分割統治 + FFT で \(O(N\log ^ 2 N)\) 時間で解くことができます．

実装例 (c++, 575ms)