すべての操作後の \(k\) の個数の期待値を \(E_k\) とします．

\(k \geq 2\) を固定し，「\(k\) が \(i\) 回目の操作で最初に現れる」という事象を考えます．このとき，\(i-1\) 回目の操作までに，操作 \(1\) はちょうど \(k-2\) 回行われ， \(i\) 回目の操作では操作 \(1\) が行われます．この事象が起こる確率は \(\binom{i-1}{k-2}p^{k-1}(1-p)^{i-k+1}\) です．以降，この事象で条件づけて考えます．

残り \(N-i-1\) 回の操作後の \(k\) の個数の期待値を \(f(N-i-1)\) とします (これは \(k\) によりません)．\(A\) の要素数が \(n\) 個，そのうち \(k\) の個数が \(c\) 個であるとき，\(1\) 回の操作後の \(k\) の個数の期待値は \(c+(1-p)\frac{c}{n}=\frac{n+1-p}{n}c\) となります．よって，\(f(N-i-1)=\frac{(N-p)\cdots(i+2-p)}{(N-1)\cdots(i+1)}\) と表されます．\(f(0)=1, f(x)=f(x-1)\frac{N-x+1-p}{N-x}\) という漸化式が成り立つので，\(f(0),f(1),\dots,f(N)\) の列挙は適切な前計算によって \(O(N)\) 時間で可能です．

これらを用いて，\(E_k\) は以下のように求められます．

\[ E_k = \sum_{i=k-1}^{N-1} \binom{i-1}{k-2}p^{k-1}(1-p)^{i-k+1}f(N-i-1) \\ = \sum_{i=0}^{N-k} \binom{i+k-2}{k-2}p^{k-1}(1-p)^{i}f(N-k-i)\\ =\frac{p^{k-1}}{(k-2)!} \sum_{i=0}^{N-k} \frac{(1-p)^i}{i!}\cdot f(N-k-i)(i+k-2)!\\ =\frac{p^{k-1}}{(k-2)!} \sum_{i=0}^{N-k} \frac{(1-p)^i}{i!}\cdot f(N-k-i)(N-(N-k-i)-2)! \]

よって，多項式 \(F(x),G(x)\) を \(F(x)=\sum_{j=0}^{N-2} f(j)(N-j-2)! x^j,\,G(x)=\sum_{j=0}^{N-2} \frac{(1-p)^j}{j!}x^j\) と定義すると，\(k\) に対する答えは \(\frac{p^{k-1}}{(k-2)!}[x^{N-k}]F(x)G(x)\) と表されます．\(F(x),G(x)\) は \(O(N)\) 時間，それらの積は高速 Fourier 変換により \(O(N\log N)\) 時間でそれぞれ求められます．AtCoder Library が使える場合，積の計算には atcoder::convolution を用いるのが便利です．

\(E_1\) は，\(E_1 = N - \sum_{k=2}^N E_k\) より求められます．