For a polynomial \(f(X)\) of \(X\), let \([X^k]f\) denote its coefficient of the \(k\)-th order.

Solution 1: Inclusion-Exclusion Principle

Let \(U=\{1,\ldots,M\}\), and for \(S\subset U\), let \(f(S)=\sum_{i\in S}\frac{C_i}{N}\).

By inclusion-exclusion principle, the probability that all the integers are written on the notebook after at most \(n\) operations is \(p(n):=\sum_{S\subset U}(-1)^{M-|S|}f(S)^n\). Thus, the probability that the \((n+1)\)-th operation contributes to the sought expected value is \(1-p(n)\), so the sought expected value equals

\(\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|}.\\\)

(Notes for mathematicians: the infinite sum absolutely converges, so one can swap the summation order at the third equal sign.) Here, if we define a DP (dynamic programming) table by

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

then we have \(\mathrm{DP}(m,k)=\mathrm{DP}(m-1,k)-\mathrm{DP}(m-1,k-C_i)\), so \(\mathrm{DP}(M,k)\) for all \(k\) can be found in a total of \(O(NM)\) time.

Interpreting this DP as operations on polynomials, we obtain \(\mathrm{DP}(m,k)=[X^k](-1)^{M-1}\prod_{i=1}^{m}(1-X^{C_i})\), so \(\mathrm{DP}(M,k)\) for all \(k\) can be obtained in a total of \(O(N(\log N)^2)\) time. Therefore, the problem has been solved.

Writer’s solution (C++)

Solution 2: Markov Chain

We distinguish the \(N\) cards by numbering them from \(1\) through \(N\). The procedure can be regarded as an absorbing Markov chain. Let the states be the sets \(S\subset\{1,\ldots,N\}\) of cards darwn so far. In the absorbing state, \(S\) contains all the cards.

For a state \(S\), let \(f(S)\) be the probability that \(S\) is visited at least one before reaching the absorbing state. By linearity of expected value, the sought expected value equals the sum of expected value of the times of transitions from each state. A transition from \(S\) either goes back to itself with probability \(\frac{|S|}{N}\) and goes to a new state with probability \(1-\frac{|S|}{N}\). Thus, the expected value of the number of operations before transitioning from state \(S\) to another is \(\displaystyle \frac{1}{1-\frac{|S|}{N}}\). Since each transition increases \(|S|\), it never goes back to an already visited state, the expected value turns out to be \(\displaystyle \sum_{S\in \mathcal{P}}\frac{f(S)}{1-\frac{|S|}{N}}\), where \(\mathcal{P}\) is the set of all the non-absorbing states. By deforming the expression, one obtains

\(\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).\)

Here, \(\displaystyle P_k:=\sum_{\substack{S\in \mathcal{P}\\|S|=k}}f(S)\) equals the probability that, when choosing \(k\) cards out of \(N\), they do not contain all kinds of cards. By considering the complementary events, one can evaluate the following DP:

\(\mathrm{DP}[m][c]=\) the number of ways to choose a total of \(c\) cards from those of \(1\)-st, \(2\)-nd, \(\ldots\), and \(m\)-th kind, so that each kind of cards is chosen at least once.

This way, all \(P_k\) can be obtained in a total of \(O(NM)\) time (with a proper optimization using cumulative sums). Interpreting this DP as polynomial operations yields

\(\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, \)

which enables us to find all \(P_k\) in a total of \(O(N(\log N)^2)\) and answer the original problem.

Writer’s solution (C++)