粉兔题解，好！
题意简述
有 $n$ 个物品，第 $i$ 个物品给定 $a_i$ 和 $b_i$。
每一个单位时间你会获得一个物品，设 $\sum_{i=1}^n a_i = \sum a, \sum_{i=1}^n b_i = \sum b$，则第 $i$ 个物品有 $\dfrac{a_i}{\sum a}$ 的概率获得。
计算第一次对于每个 $i$ 都有第 $i$ 个物品获得至少 $b_i$ 个的期望时间。
$n, \sum a, \sum b\le 400$。
主要思路
先 min-max 容斥，转化为对于每个非空子集 $S$ 求第一次自己中的任意一个物品获得至少 $b_i$ 个的期望时间，对答案贡献为 $(-1)^{|S|+1}$。
也就是满足子集 $S$ 中的所有物品获得的数量都少于 $b_i$ 个的期望时刻数量，加上 $1$。可以把开始无物品的状态也算作 $1$ 个时刻，即可略去 $+1$。
考虑计算这个期望时刻数量（包括初始时刻）。
即对每种物品获得的状态，计算这种状态在所有可能情况下的期望次数（包括初始时刻），再求和。
不难发现，一旦第一次变成了某种状态，只要再次获得 $S$ 中的物品，状态就会改变。
所以一个状态将期望持续 $\dfrac{\sum a}{\sum\limits_{i\in S}a_i}$ 个时刻。于是只用考虑每种情况的出现概率即可，这时就可以不考虑 $S$ 以外的物品的影响了。
假设第 $i$ 个物品获得了 $0\le x_i< b_i$ 次，$i\in S$，那么达到这种状态就是存在一个获得 $S$ 中的物品前缀满足 $i$ 恰好出现了 $x_i$ 次。
令 $X=\sum\limits_{i\in S}x_i,C=\sum\limits_{i\in S}a_i$，则概率即为 $X!\displaystyle\prod\limits_{i\in S}\left(\dfrac{a_i}{C}\right)^{x_i}\dfrac{1}{x_i!}=\displaystyle\dfrac{X!}{C^X} \prod_{i\in S} \frac{a_i^{x_i}}{(x_i)!}$。阶乘来源于多重组合数。
然后你发现这个状态只关系 $X, C$ 了。不妨设 $f(C, X)$ 为 $(-1)^{|S|+1}\displaystyle\prod_{i\in S} \frac{a_i^{x_i}}{(x_i)!}$ 的期望。
于是转移就非常简单了：加入 $i$ 时，枚举 $0\le x_i< b_i$，$f(C, X) \leftarrow^{-} f(C - a_i, k - x_i)\dfrac{a_i^{x_i}}{x_i!}$。
这样依次加入 $n$ 个物品，每次复杂度为 $O(b_iXC)$ 暴力，总时间复杂度 $O((\sum b)^2\sum a)$。
最后求答案的时候记得对于 $f(C, X)$ 乘上 $\dfrac{X!}{C^{X - 1}\sum a}$ 的系数。
在 EGF 层面考虑，其实这个东西就大概是个卷积形式。
然后也确实有一个暴推生成函数的做法，大概最后能化成 $\sum\limits_{n\ge 0}n![z^n]\sum\limits_{i, j}c_{i, j}z^i e^{jz}$ 之类的东西，然后那个 $j$ 是一堆概率乘一起，所以这玩意就收敛了……
参考代码
1 |
|