提前了一个月,就做掉了这题,不过还是庆祝一下吧。(
考虑 dp。令 \(f_{u,i}\) 表示货架 \(u\) 还剩 \(i\) 罐未被吃的蜂蜜的概率。答案就是 \(\sum f_{u,0}\)。
考虑一次修改 \(u\to v\),由于被移动的蜜罐都被吃了,所以 \(v\) 的 \(f\) 数组不变,只需要考虑 \(f_u\) 的变化。
枚举吃掉了 \(j\) 个有蜜的蜜罐:
\[f_{u,i}\cdot\frac{\dbinom{i}{j}\dbinom{a_u-i}{k-j}}{\dbinom{a_u}{k}}\to f_{u,i-j} \]然后就做完了,复杂度 \(O(qk^2A)\)。
标签:Piglet,蜜罐,CF248E,Birthday,考虑,dbinom From: https://www.cnblogs.com/Ender32k/p/17792930.html