\(X\) の多項式 \(f(X)\) に対し、その \(k\) 次の係数を \([X^k]f\) と表します。

解法１：包除原理

\(U=\{1,\ldots,M\}\) とし、\(S\subset U\) に対し\(f(S)=\sum_{i\in S}\frac{C_i}{N}\) とします。

包除原理より、高々\(n\) 回ですべての数がノートに書かれた状態になる確率は \(p(n):=\sum_{S\subset U}(-1)^{M-|S|}f(S)^n\) です。よって、\(n+1\) 回目の操作が求める期待値に寄与する確率は \(1-p(n)\) であり、求める期待値は

\(\displaystyle \sum_{n\geq 0}(1-p(n))\\ =\sum_{n\geq 0}(1-\sum_{S\subset U}(-1)^{M-|S|}f(S)^n)\\ =\sum_{n\geq 0}\sum_{S\subsetneq U}(-1)^{M-1-|S|}f(S)^n\\ =\sum_{S\subsetneq U}\sum_{n\geq 0}(-1)^{M-1-|S|}f(S)^n\\ =\sum_{S\subsetneq U}(-1)^{M-1-|S|}\sum_{n\geq 0}f(S)^n\\ =\sum_{S\subsetneq U}(-1)^{M-1-|S|}\frac{1}{1-f(S)}\\ =\sum_{k=0}^{N-1}\sum_{f(S)=\frac{k}{N}}(-1)^{M-1-|S|}\frac{1}{1-\frac{k}{N}}\\ =\sum_{k=0}^{N-1}\frac{N}{N-k}\sum_{f(S)=\frac{k}{N}}(-1)^{M-1-|S|}\\\)

となります（数学者向け注：この無限和は絶対収束しているので3つ目の等号において順序を入れ替えて良い）。ここで

\(\displaystyle \mathrm{DP}(m,k)=\sum_{\substack{S\subset\{1,\ldots,m\}\\f(S)=\frac{k}{N}}}(-1)^{M-1-|S|}\)

と定めると、\(\mathrm{DP}(m,k)=\mathrm{DP}(m-1,k)-\mathrm{DP}(m-1,k-C_i)\) となることから、全ての \(k\) に対する \(\mathrm{DP}(M,k)\) を \(O(NM)\) 時間で求めることができます。

また、このDPを多項式演算として解釈することで、 \(\mathrm{DP}(m,k)=[X^k](-1)^{M-1}\prod_{i=1}^{m}(1-X^{C_i})\) となることから、全ての\(k\) に対する \(\mathrm{DP}(M,k)\) を \(O(N(\log N)^2)\) 時間で求めることができます。以上により問題が解けました。

Writer解(C++)

解法２：マルコフ連鎖

\(N\) 枚のカードに \(1\) から \(N\) の番号をつけ区別することにします。一連の操作は吸収マルコフ連鎖とみなせます。今まで \(1\) 度以上引いたカードの集合 \(S\subset\{1,\ldots,N\}\) を状態とします。\(S\) が全種類のカードを含むときを吸収状態となります。

状態 \(S\) に対して、吸収状態に至るまでに \(1\) 度以上状態 \(S\) になる確率を \(f(S)\) とします。期待値の線形性より求める期待値は各状態から遷移する回数の期待値の和に等しくなります。\(S\) からの遷移では、確率 \(\frac{|S|}{N}\) で自身へ戻り、\(1-\frac{|S|}{N}\) の確率で新たな状態に遷移します。よって、状態 \(S\) から別の状態に遷移するまでの操作回数の期待値は \(\displaystyle \frac{1}{1-\frac{|S|}{N}}\) となります。遷移により \(|S|\) が増加することから再び同じ状態に戻ることはないので、求める期待値は \(\displaystyle \sum_{S\in \mathcal{P}}\frac{f(S)}{1-\frac{|S|}{N}}\) となります。ここで \(\mathcal{P}\) は吸収状態でない全ての状態からなる集合です。この式を変形すると

\(\displaystyle \sum_{S\in \mathcal{P}}\frac{f(S)}{1-\frac{|S|}{N}}\\ =\sum_{k=0}^{N-1}\sum_{\substack{S\in \mathcal{P}\\|S|=k}}\frac{f(S)}{1-\frac{|S|}{N}}\\ =\sum_{k=0}^{N-1}\frac{N}{N-k}\sum_{\substack{S\in \mathcal{P}\\|S|=k}}f(S)\)

となります。ここで、\(\displaystyle P_k:=\sum_{\substack{S\in \mathcal{P}\\|S|=k}}f(S)\) は「\(N\) 枚の中からカードを \(k\) 枚選んだとき、それが全種類のカードを含まない確率」 と等しくなることから、余事象を考えることで

\(\mathrm{DP}[m][c]=\) \(m\) 種類目までのカードから、各種類のカードを \(1\) 枚以上、全体で \(c\) 枚選ぶような方法の数

というDPにより、(累積和を用いた適当な高速化の下) \(O(NM)\) 時間で全ての \(P_k\) を求めることができます。このDPを多項式演算として解釈することで、

\(\displaystyle P_k= 1-[X^k]\frac{1}{\binom{N}{k}}\prod_{i=1}^{M}\sum_{j=1}^{C_i}\binom{C_i}{j}X^j \)

を得、\(O(N(\log N)^2)\) 時間で全ての \(P_k\) を求めることができ、元の問題に答えることができます。

Writer解(C++)