Min-Max 容斥

前置知识

• 期望具有线性性。

设 $\mathbf{E}(x)$ 表示事件 $x$ 的期望，则有

$$\mathbf{E}(\sum x)=\sum \mathbf{E}(x)$$

即：总体的期望等于期望的和。

应用实例：模拟赛 #38 T2：

给定 $n$ 个点，每个点有 $w_u$，从 $u$ 走到儿子 $v^{\prime }$ 的概率是 $w_{v^{\prime }}÷\sum w_v$，经过一个点的得分是 $a_u$，走到叶子结束，$q$ 次修改一个点的 $a_u,w_u$，求从根出发的得分期望。

sol

考虑拆成每个点的贡献和，走到点 $u$ 的期望只与自己父亲节点的 $w$ 和 $\sum w$ 有关，并且和 $a_u$ 都是乘法关系，那么修改一个节点就对他的子树进行区间乘修改，区间求和即可，线段树做到 $O((n+q)\log n)$。

Min-Max 容斥

$$\underset{i\in S}{max}i=\sum _{T\subseteq S}(-1{)}^{|T|+1}\underset{i\in T}{min}i$$$$\underset{i\in S}{min}i=\sum _{T\subseteq S}(-1{)}^{|T|+1}\underset{i\in T}{max}i$$

考虑证明第一条，设 $S$ 从小到大排序后是 $S_{1\dots n}$，只需证明只剩 $S_n$ 被留下即可。

考虑 $S_i$ 在等式右侧作为 $min$ 的出现次数，那么显然只能再选 $S_{i+1\dots n}$ 这 $n-i$ 个数，记 $n-i=m$，那么其中 $|T|mod2=1$ 的个数是 $(\genfrac{}{}{0ex}{}{m}{0})+(\genfrac{}{}{0ex}{}{m}{2})+\dots$，$|T|mod2=0$ 的个数是 $(\genfrac{}{}{0ex}{}{m}{1})+(\genfrac{}{}{0ex}{}{m}{3})+\dots$，两者相等，故 $\mathrm{\forall }i<n,S_i$ 的贡献均被容斥掉，只剩 $S_n$ 作为最小值被统计一次，容斥系数为 $1$，证毕。

这玩意乍一看没什么用，但是结合期望能得到

$$\underset{i\in S}{max}\mathbf{E}(i)=\sum _{T\subseteq S}(-1{)}^{|T|+1}\underset{i\in T}{min}\mathbf{E}(i)$$

请看题目。

刷题总结

1. P3175 [HAOI2015] 按位或

每个位上的 $1$ 出现后就不会消失，根据期望的线性性，相当于求 $[0,n)$ 位中最晚出现的 $1$ 的期望时间。

这个不好做，Min-Max 容斥一下考虑求每个数位子集 $T$ 中，最早出现的 $1$ 的期望时间。

但是判断取的这个数是否和 $T$ 有交是困难的，那么再转换一下，考虑求与 $T$ 无交的期望时间。

那么就相当于求 $T$ 的补集的子集的期望和，使用高维前缀和解决，这一部分的时间复杂度是 $O(n\times 2^n)$。

最后枚举 $T$ 算 Min-Max 容斥答案，这一部分的时间复杂度是 $O(2^n)$。