题解：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)。

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