526互联

AtCoder Beginner Contest 331 G - Collect Them All【概率期望+容斥+多项式】

发布时间 2023-12-10 16:32:52作者: Chloris_Black

题目链接：ABC331_G

写在前面 将来如果回顾这道题，建议自己看完题意一定先重新推一遍。如果还是不够熟练，多去做一些同类型的题目吧。

题意：

盒子里有 \(N\) 张卡片，每张卡片上写着一个数字，数字的范围是 \(1,...,M\)，写着数字 \(i\) 的卡片有 \(C_i\) 张\(（C_i>0）\)。有放回地抽取卡片，每次抽取一张，问抽到过全部 \(M\) 种数字的期望抽取次数是多少？
\((1\leq M\leq N\leq2\times10^5)\)

思路梳理：

概率期望

首先转化该题的概率期望部分。
对于这种“询问抽到过全部 \(M\) 种物品的期望次数”的期望类题目，经典的套路是将期望转化为概率的后缀和。

设 \(E(i)\) 为抽取 \(i\) 次恰好抽齐的期望次数， \(P(i)\) 为抽取 \(i\) 次恰好抽齐的概率，则有：

\(Ans = \sum\limits_{i=1}^{\infty}E(i) = \sum\limits_{i=1}^{\infty}P(i)\times i\)

设 \(suf(i)\) 为 \(P(i)\) 的后缀和，即 \(suf(i) = \sum\limits_{j=i}^{\infty}P(j)\)

于是又有：\(\sum\limits_{i=1}^{\infty}P(i)\times i = \sum\limits_{i=1}^{\infty}suf(i)\)

考虑 \(suf(i)\) 的实际含义，作为 \(P(i)\) 的后缀和，它表示抽取至少 \(i\) 次才抽齐的概率，也就是抽取 \(i-1\) 次都没有抽齐的概率。

设 \(P_1(i)\) 为抽取 \(i\) 次都没有抽齐的概率，于是得到：\(Ans = \sum\limits_{i=1}^{\infty}suf(i) = \sum\limits_{i=0}^{\infty}P_1(i)\)

容斥

现在来考虑 \(P_1(i)\) 该如何求得。先枚举抽取次数 \(i\) ，再枚举被抽到数字的集合 \(T\)（\(T\varsubsetneqq U\)，此处计算没有抽齐的情况，因此 \(T\) 为全集 \(U\) 的真子集）。设 \(f(i,T)\) 为抽取 \(i\) 次抽到数字的集合至多为 \(T\) （即没有抽到 \(T\) 集合外的数字）的概率， \(F(T)\) 为抽到数字的集合恰好为 \(T\) 的概率(包含抽取 \(0\sim \infty\) 次的情况），则答案为：

\(Ans = \sum\limits_{i=0}^{\infty}P_1(i) = \sum\limits_{i=0}^{\infty}\sum\limits_{T\varsubsetneqq U}^{\infty}f(i,T) = \sum\limits_{T\varsubsetneqq U}^{\infty}F(T)\)

现在将答案表示成了一个与集合有关的概率，但 \(F(T)\) 是一个不好计算的东西。“恰好”难于计算的情况下，可以考虑容斥的思想，将容易计算的“至多/至少”通过容斥的方法转化成难于计算的“恰好”。

设 \(G(T)\) 为抽到数字的集合至多为 \(T\) （即没有抽到 \(T\) 集合外的数字）的概率，发现 \(G(T)\) 是容易计算的:

\(G(T)=\sum\limits_{i=0}^{\infty}\left(\frac {1}{n} \times \sum\limits_{x\in T}C_x\right)^i\)

可以发现 \(G(T)\) 为等比级数求和，于是有：

\(G(T)= \frac {\sum\limits_{x\in T}C_x}{n-\sum\limits_{x\in T}C_x}\)

建立“至多/至少”和“恰好”的关系，设 \(C(T)\) 为 \(F(T)\) 需要产生的贡献， \(coef(T)\) 为容斥系数，有容斥方法：

\(\sum\limits_{T\varsubsetneqq U}^{\infty}F(T)\times C(T) = \sum\limits_{T\varsubsetneqq U}^{\infty}G(T)\times coef(T)\)

由上面的答案计算式，可以得到 \(C(T) = 1\)。因为“至多”包含“恰好”，\(G(T)\) 包含 \(F(T)\)， 在容斥中从包含的一方向被包含转移，得到 \(coef(T) = C(T) - \sum\limits_{S\varsubsetneqq T}coef(S)\)。