题解：uoj390 百鸽笼

先把问题转化为：加入 $\sum a_i$ 个人，计算最后一次插入是第 $i$ 个笼子的概率。

考虑最后一次插入不好钦定，我们容斥成若干个笼子在他之后还有插入的概率。

具体来说，我们枚举集合 $S$，求钦定在第 $i$ 个笼子插满的时候，$S$ 集合都 没有 被插满的概率。首先 $U-\{i\}-S$ 的部分不管，所以对概率没有贡献。考虑枚举 $S$ 中每个笼子在 $i$ 插满的时候插了 $b_j$ 个，那么概率为 $\prod_{j\in S} \frac{1}{b_j!}\times \frac{(\sum_{j\in S}b_j+a_i-1)!}{(a_i-1)!}\times (\frac{1}{|S|+1})^{\sum_{j\in S}b_j+a_i}$。

感受一下这个式子，前面两项是排列组合的方案数：一个总长为 $\sum_{j\in S} b_j+a_i$ 的序列，要求 $j$ 出现了恰好 $b_j$ 次，且最后一个是 $i$ 的方案数；后一项是总概率，因为在这些操作时每个笼子被选的概率都恰好是 $\frac{1}{|S|+1}$。

观察发现，这个式子只跟 $i,\sum_{j\in S}b_j,|S|$ 有关，直接 dp 即可。时间复杂度 $O(n^6)$。

利用到了概率的特殊性，在容斥时可以忽略很多复杂部分。