称题目中的 \(c_i\) 为 \(a_i\)，令 \(c_i\) 为第 \(i\) 种颜色的出现次数，令 \(C\) 为颜色总数。固定 \(k\)，令 \(t_i=1\)，如果颜色 \(i\) 被选择了一次及以上，否则为 \(0\)，则答案为 \(\textbf{E}(\sum t_i)=\sum\textbf{E}(t_i)=\sum\frac{\binom{n}{k}-\binom{n-c_i}{k}}{\binom{n}{k}}\)。
对于一个固定的 \(k\)，上式的取值只取决于 \(c_i\) 的大小，令 \(s_x\) 为 \(c_i=x\) 的 \(i\) 的数量。则答案写为 \(\sum s_x\times\frac{\binom{n}{k}-\binom{n-x}{k}}{\binom{n}{k}}\)。
分析复杂度，\(n=\sum i\times s_i\)，因此单次计算最劣 \(\Theta(\sqrt n)\)。
「atcoder - ABC215G」Colorful Candies 2
原文：https://www.cnblogs.com/orchid-any/p/15174477.html