设 $P(S)$ 为钦点 $S$ 中所有元素都在 1 之后挂掉的概率,显然:

$$
P(s) = \frac{a_1}{sum(S) + a_1}
$$

于是我们可以发现最后答案为:

$$
ans = \sum\limits_{S \in [2, n]} P(S) (-1)^{|S|}
$$

于是分治 + NTT 即可。

至此除斗地主外的所有 PKUWC 2018 题目已经订正完毕,祝也去参加 PKUWC 的读者和自己 RP = $+\infty$ qwq!

分治套 NTT 优化仙人掌 DP 题目。往这个方向想其实不是很难推,于是就懒得写题解直接贴代码了 qwq。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×