0-indexed で置き換えて考えます．

• はじめ \(A=(0)\) である．
• 各操作では確率 \(p\) で操作 1 を，確率 \(1-p(=q)\) で操作 2 を行う．
  • 操作 1 ：\(A\) に現れない最小の非負整数を \(A\) に追加．
  • 操作 2 ：\(A\) の要素をランダムに一つ選び，同じ値を \(A\) に追加．

\(i\) 回目の操作を終えたときの \(k(\geq 1)\) の個数の期待値を \(a_{k,i}\) としたとき，以下が成り立ちます．

\[a_{k,0}=0,\quad a_{k,i}=\underbrace{p^kq^{i-k}\binom{i-1}{k-1}}_{\text{(i)}}+\underbrace{\frac{q}{i}\cdot a_{k,i-1}}_{\text{(ii)}}+a_{k,i-1}\ (i\geq 1)\]

ただし \(0\leq r\leq n\) でないとき \(\binom{n}{r}=0\) であるものとします．(i), (ii) はそれぞれ操作 1, 2 により増える個数の期待値に対応しています．

多項式 \(f_i(x)=\sum_{k=1}^{N-1}a_{k,i}x^k\) を考えると，上の関係式は下のように表されます．

\[f_0(x)=0,\quad f_i(x)=px(px+q)^{i-1}+\left(1+\frac{q}{i}\right)f_{i-1}(x)\]

特に \(f_{N-1}(x)\) は以下の形に表せます．

\[f_{N-1}(x)=\sum_{i=1}^{N-1}px(px+q)^{i-1}\prod_{j=i+1}^{N-1}\left(1+\frac{q}{j}\right)\]

これは Taylor Shift により \(O(N\log N)\) 時間で計算できる形です．

上記では \(k=0\) について考えていませんが，\(a_{0,i}\) について同様の関係式が成り立つことから，あるいは全ての \(k\) についての期待値の総和が \(N\) であることから求められます．