谨以此文记录我的 OI 生涯的第一次向 PKU 冲刺的机会。

持续更新。

最近有人用脚本（或其他）方式在这个博客刷大量垃圾评论骚扰。我有一些内容想留给那位同学：

学习 @GNAQ 大佬，在博客里推荐一些歌 qwq…

《心愿》 by 王泽 & 杨颖 & 乔媛 & 唐景莲

一首略有点悲伤的校园歌曲，记录了一代人的青春岁月。

不知不觉，这个博客已经有了 10000 的访客数和 30000 的访问量，memset0.cn 也陪我走过了将近一个年头。
想当初的自己看到 rxz 哥哥的博客非常帅气，经历几番波折终于折腾出了自己的博客。
而那时候，这篇博客的内容也非常肤浅（大概也就初学线段树的水平 233），到现在学了越来越多的知识，能够写出稍微有点意义的题解了 qwq… 自己也从一个普及组选手，逐渐进化为一个打提高的菜鸡。

回首过往，浮想联翩。
如今 PKUWC 在即，也是决定我命运的其中一站，期盼着的未来，会是那个美好的结局吗？

设 $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！

大于 $\max(c_i c_j)$ 的 $ v = \gcd(c_i) \ (i \in [1, n])$ 的倍数都可以被取到。
先做关于 $v$ 的循环卷积，然后背包一下把中间相差的部分补上即可。
由于要求对 $10^9+7$ 取模，所以需要 MTT。

每个点维护线性基，线段树的两个子节点合并的时候直接把一个点的暴力插入到隔壁即可。

考虑 Min-Max 容斥，$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间，则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出，但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式，推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实，需要处理出子集卷积即可 AC 。

同理可 Min-Max 容斥：

$$
\min(S) = \frac{1}{1 - \sum\limits_{S’ \subseteq S} \sum\limits_{u \in S’} p_u}
$$

FWT 一波即可。

考虑 Min-Max 容斥。用 $\min(S)$ 表示 $S$ 中出现至少一个元素的期望时间，用 $\max(S)$ 表示 $S$ 中每一个元素都出现的期望时间。

则：

$$
\begin{aligned}
\min(S) &= \frac{1}{\sum\limits_{i \in S} p_i} \\
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

答案显然是让我们求 $\max(\texttt{全集})$ ，故状压一下即可。