题意
有 \(n\) 个颜色，每个颜色有 \(m\) 个球。在这 \(nm\) 个球中摸球，不放回，问取完每一种颜色的 \(m\) 个球的期望次数。
思路
方法：Min-Max 容斥
我们记 $$\binom{a}{b{m}}=\binom{a}{\underbrace{m,m,\cdots,m}_{b个m}}=\frac{a}{(m!)^b}$$
为把 \(a\) 个数分成 \(b\) 组，每组 \(m\) 个的方案数。其中 \(a=bm\)。
那么显然的，总方案数为：
\[\binom{nm}{n\{m\}} \]我们考虑取完第 \(i\) 种颜色的时间为 \(x_i\)，则答案为 \(E(\min(\{x_i\}))\)。
那么可以用 Min-Max 容斥。由于每种颜色本质是一样的，所以我们只枚举取完的颜色个数。于是：
\[E(\min(\{x_i\}))=\sum_{i=1}^n(-1)^{i+1}\binom niE(\max(\{x_1,\cdots,x_i\})) \]现在枚举最后一个球出现的时刻，则有：
\[\begin{align*} E(\min(\{x_i\}))=&\sum_{i=1}^n(-1)^{i+1}\binom niE(\max(\{x_1,\cdots,x_i\}))\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\binom{nm}{n\{m\}}^{-1}\sum_{j\le nm}j\binom{j-1}{im-1}\binom{im}{i\{m\}}\binom{(n-i)m}{(n-i)\{m\}}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\binom{nm}{n\{m\}}^{-1}\binom{im}{i\{m\}}\binom{(n-i)m}{(n-i)\{m\}}\sum_{j\le nm}j\binom{j-1}{im-1}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\frac{im!(nm-im)!}{nm!}\sum_{j\le nm}j\binom{j-1}{im-1}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\binom{nm}{im}^{-1}\sum_{j\le nm}j\binom{j-1}{im-1}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\binom{nm}{im}^{-1}\sum_{j\le nm}im\binom{j}{im}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\binom{nm}{im}^{-1}im\sum_{j\le nm}\binom{j}{im}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom ni\binom{nm}{im}^{-1}im\binom{nm+1}{im+1}\\ =&\sum_{i=1}^n(-1)^{i+1}\binom niim\frac{nm+1}{im+1}\\ =&(nm+1)\sum_{i=1}^n(-1)^{i+1}\binom ni\frac{im}{im+1}\\ =&(nm+1)\sum_{i=1}^n(-1)^{i+1}\binom ni\left(1-\frac{1}{im+1}\right)\\ =&(nm+1)\left(\sum_{i=1}^n(-1)^{i+1}\binom ni-\sum_{i=1}^n(-1)^{i+1}\binom ni\frac{1}{im+1}\right)\\ =&(nm+1)\left(\sum_{i=0}^n(-1)^{i+1}\binom ni+1-\sum_{i=0}^n(-1)^{i+1}\binom ni\frac{1}{im+1}-1\right)\\ =&(nm+1)\left(-\sum_{i=0}^n(-1)^{i}\binom ni-\sum_{i=0}^n\binom ni\frac{(-1)^{i+1}}{im+1}\right)\\ =&(nm+1)\left(-[n=0]-\sum_{i=0}^n\binom ni\frac{(-1)^{i+1}}{im+1}\right)\\ =&(nm+1)\left(-\sum_{i=0}^n\binom ni\frac{(-1)^{i+1}}{im+1}\right)\\ =&(nm+1)\sum_{i=0}^n\binom ni\frac{(-1)^{i}}{im+1}\\ \end{align*} \]根据《具体数学》中 5.3 处理的技巧 中的式子有：
\[\sum_{i=0}^n\binom ni\frac{(-1)^i}{i+x}=\frac{n!}{x(x+1)\cdots(x+n)}=x^{-1}\binom{x+n}{n}^{-1} \]所以
\[\begin{align*} E(\min(\{x_i\}))=&(nm+1)\sum_{i=0}^n\binom ni\frac{(-1)^{i}}{im+1}\\ =&\frac{nm+1}{m}\sum_{i=0}^n\binom ni\frac{(-1)^{i}}{i+\frac 1m}\\ =&\frac{nm+1}{m}\cdot\frac{n!}{\frac 1m(\frac 1m+1)\cdots(\frac 1m+n)}\\ =&\frac{nm+1}{m}\cdot\frac{n!m^{n+1}}{(m+1)(2m+1)\cdots(nm+1)}\\ =&\frac{(nm+1)n!m^n}{\prod_{i=1}^n(im+1)}\\ \end{align*} \]使用快速阶乘算法计算 \(\prod_{i=1}^n(im+1)\)，分段打表计算 \(n!\) 即可。
标签：原神,frac,nm,ni,sum,cats,im,随机,binom From： https://www.cnblogs.com/ninler/p/18384102