min-max 容斥_算法

min-max 容斥

式子：

$$E[\max_{i=1}^n X_i]=\sum_{S\sube[n],|S|\ge 1}(-1)^{|S|+1}E[\min\{X_i\}_{i\in S}]$$

原版式子是把 $E$ 去掉，把 $E$ 加上是因为它通常出现在期望线性性中。

记住这个式子的方式是记住大小为 $1$ 的集合贡献是正的。

证明：由期望的线性性，只需对实数 $x_1\le x_2\le \cdots\le x_k$ 证明。则左式为 $x_k$。

考虑每个 $x_i$ 对右式的贡献：

$$\sum_{j=1}^{n-i+1}\binom{n-1}{j-1}(-1)^{j-1}=(1-1)^{n-i}=[n=i]$$

扩展：

$$\text{kmax}(S)=\sum_{T\sube S,|T|\ge1}\binom{|T|-1}{k-1}(-1)^{|T|+k}\min(T)$$

记住式子的方式就是改一改上面的柿子。

通常用到 mm 容斥的时候并不是直接问你最值，比如说：

有 $n$ 种物品，每个时刻等概率获得一个，求给定某个集合被全部获得的期望时刻。

全部获得的时刻就是最晚的元素被获得的时刻，设第 $i$ 个元素被获得的时刻是 $X_i$，则求 $\max X_i$。

很难做，但是 $\min X_i$ 很好做，就是 $\frac{n}{|S|}$，于是我们就会做 $\max$ 了。

有很多时候也不一定是集合题，比如上面这个题我们只关心集合大小，那我们直接关心大小即可。

P5643 [PKUWC2018] 随机游走

给定一棵 $n$ 个结点的树，你从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 $Q$ 次询问，每次询问给定一个集合 $S$，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。

特别地，点 $x$（即起点）视为一开始就被经过了一次。

答案对 $998244353 $ 取模。

$x\le n\le 18,Q\le 5000$。

利用上面的 trick，我们考虑怎么求 $E[\min S]$，设 $f_{i,S}$ 为 $i$ 走到 $S$ 中任意一个点的期望步数，则我们可以列方程，大概是一个树上高消的形式。

忘了树上高消是啥形式了：每个点的转移式是 $f_i=A_if_{fa_i}+B_i$，其中 $A_i,B_i$ 是从下往上递推。

大概推一下吧：

$$\begin{aligned}f_x&=\frac{1}{d_x}(f_{fa_x}+1+\sum_{fa_v=x}(f_v+1))\\&=\frac{1}{d_x}(f_{fa_x}+1+\sum_{fa_v=x}(A_vf_x+B_v+1))\end{aligned}$$

（根的转移式没有 $f_{fa_x}+1$。）

合并同类项之后就是 $(d_x-\sum A_v)f_x=f_{fa_x}+1+\sum (B_v+1)$，将 $f_x$ 的系数除过去不难得到 $A,B$ 的递推式。

接下来我们考虑用一些 $E[\min S]$ 求出 $E[\max S]$，你发现直接令 $f'_S=(-1)^{|S|+1}f_S$ 然后高维前缀和就好了。

这个题我们还钦定了一些 $f$，但也无需很特殊地处理它们，直接相当于 $f_x=0f_{fa_x}+0$ 即可。

P3175 [HAOI2015] 按位或

刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行或（C++,C 的 |，pascal 的 or）操作。选择数字 $i$ 的概率是 $p_i$。保证 $0\leq p_i \leq 1$，$\sum p_i=1$ 。问期望多少秒后，你手上的数字变成 $2^n-1$。

$n\le 20$。

很显然，一样的套路，求全集全部出现的时间，我们转为求每个集合中至少一个数第一次出现的时间。

后者比较简单，不断选直到与其有交的集合被选中即可，这是一个几何分布，注意除 $0$ 要变成 inf。

与其有交的集合的概率和怎么求？用全集减掉无交的即可（补集的子集）。

[ARC185D] Random Walk on Tree