做题记录

[ABC331G] Collect Them All

题意：有 \(m\) 种颜色，第 \(i\) 种颜色被抽到的概率是 \(\frac{c_i}{n}\)，求期望多少次抽卡能将所有颜色集齐。
数据范围：\(1\le m\le n\le 2\times 10^5\)。

\(\texttt{min-max}\) 容斥。

设全集 \(U=\{1,2,\cdots,m\}\)，则有：\(E(\max\{t_i\})=\sum_{T\in U}(-1)^{|T|+1}E(\min\{T\})\)。

考虑求 \(E(\min\{T\})\)，每个颜色 \(j\in T\) 被抽到的概率是 \(\frac{c_j}{n}\)，概率和期望互为倒数，所以期望抽取次数为 \(\frac{n}{c_j}\)，则 \(E(\min\{T\})=\frac{n}{\sum_{j\in T}c_j}\)。

所以 \(E(\max\{t_i\})=n\sum_{T\in U}\dfrac{\left(-1\right)^{|T|+1}}{\sum_{j\in T}c_j}\)。

设 \(f(i,j)\) 表示考虑前了 \(i\) 个元素，这些元素的 \(c\) 的和为 \(j\)，\((-1)^{|T|+1}\) 的和。显然 \(f_{i,j}=f_{i-1,j}-f_{i-1,j-c_i}\)。

则 \(E(\max\{t_i\})=n\sum_{i=0}^n\frac{f(m,i)}{i}\)。

然后剩下是 NTT 的部分了，开摆。