Codeforces 248E: Piglet's Birthday
1. 题目大意
有\(n\)个柜子，第\(i\)个柜子里有\(a_i\)个装满了蜜的蜜罐。有\(q\)个操作，每次操作给出\(u\)，\(v\)，\(k\)，然后在第\(u\)个柜子里随机选取\(k\)个蜜罐吃完后放到第\(v\)个柜子里。每次操作后你需要输出蜜罐全空的柜子的期望数量。
2. 数据范围
\( 1 \le n \le 10^5 \)
\( 0 \le a_i \le 100 \)
\( 1 \le q \le 10^5 \)
\( 1 \le k \le 5 \)
3. 题解
记\( prob_{i, j} \)为第\(i\)个柜子上有\(j\)个非空蜜罐的概率，则答案显然为\( \sum_{i = 1}^n prob_{i, 0} \)。
容易发现对于一个操作\((u, v, k)\)，只有\(prob_{u, \ast}\)会被更新。考虑每次从柜子\(u\)删除一个蜜罐，那么删除之后的\(prob_{u, \ast}\)是很好计算的。将这个过程重复\(k\)次即可。
4. 时空复杂度
时间复杂度：\( O( mak ) \)
空间复杂度：\( O( na ) \)
5. 代码
代码在这里。
