minmax容斥
用途
已知集合的最小值 (期望) 求最大值
$eg:$ $n$ 个元素，每个元素出现概率 $p_i$，求每个元素都出现的期望时间
结论
即
证明
设容斥系数 $g\left(|T|\right)$
即 $\displaystyle{\max\{S\}=\sum_{T\subset S}g\left(|T|\right) \min\{T\}}$
考虑当排名为 $k$ 的数作为集合 $T$ 的最小值时，集合 $T$ 中所有值都 $\geq k$
所以对于第$k$大数 ， 在大小为 $|T|$ 的集合中， $\max$ 的选取方案为 $\displaystyle{\binom{k-1}{|T|-1}}$
考虑集合大小为 $1\sim k$ ，则第 $k$ 数的总贡献为
$\displaystyle{\sum_{i=1}^k \binom{k-1}{i-1}} * g(i)=[k=1] \qquad \text{即只有最大值对 max 有贡献}$
由二项式反演得
变式
由 $\max \Rightarrow \max$
扩展 $\min\max容斥$
证明
目的是找到容斥系数满足 $\text{kthmax}\{S\}=\sum_{T\subseteq S} f(|T|) \min\{T\}$
考虑第 $x$ 大元素，受原式启发得到
例题
-
题意
设 $\min\{S\}$ 表示二进制数 $S$ 中，第一个元素变为 $1$ 所需时间，$\max\{S\}$ 表示最后一个元素变为 $1$ 所需时间
题为求 $E(\max\{U\})$ ,其中 $U$ 为全集，$U=2^n-1$
解
由公式易知 $\displaystyle{E(\max\{U\})=\sum_{S\subseteq U}(-1)^{|S|-1} \ \sum E(\min\{S\})}$
$\therefore$ 求 $\min$
-
题意:
给出一棵树，从根节点出发每次等概率选择并走向一条相邻边
多次询问中，每次给定点集 $S$ ,求从根出发直到 $S$ 中所有点至少经过一次的期望步数
解:
由 $\min-\max$ 容斥得：$\displaystyle{E[ \max(S’) ]=\sum_{T’\in S’}(-1)^{|T’|+1}E[ \min(T’) ]}$
易知 $E[ \max(S’) ]$ 表示走完集合 $S$ 期望步数， $E[ \min(S’) ]$ 表示第一次走到集合 $S$ 的期望步数
设 $f_{S,x}$ 表示从 $x$ 出发，第一次访问到集合 $S$ 的期望步数
考虑预处理所有 $f_{S,x}$
设 $f_x$ 为点 $x$ 到 $S$ 的最早期望时间
对于 $x\in S$ 有 $f_x=0$
对于 $x\not\in S$ 有 $\displaystyle{f_x=1+\frac{1}{\deg x}\sum_{(x,y)\in E} f_y }$
这里需要 $O(n^3)$ 的高斯消元，考虑到特殊的树形结构，以起点 $root$ 为根，用一次函数分离父子关系
即设 $\displaystyle{f_x=f_{fa_x} \times A_x + B_x }$
$\therefore$ 对于 $x \not\in S$ 有 $\displaystyle{f_x=1+\frac{1}{\deg x} \left(f_{fa_x} + \sum_{y\in son_x}(A_y\times f_x + B_y) \right) }$
化简得
由此，对于给定的询问点集 $S$ ,答案就是 $\sum_{T\in S} (-1)^{|T|+1} f_{T,root}$
再考虑优化询问
由 $n\leq 18$ 提示可以状压点集，并预处理对于每个点集 $S$ 的 $\sum_{T\in S}(-1) ^{|T|+1} f_{T,root}$
那么预处理高维前缀和即可