感谢 lyc 哥哥上次给我讲了一下…然而我并没有听懂,只能自己再去学了一遍
Min-Max 容斥:
$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
$$
可以用二项式反演证明:构造容斥函数 $f(x)$ 使得
$$
\max(S) = \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|)
$$
考虑每个 $S’ \subseteq S$ 中 $\min(S’) = a_{x+1}$ 对答案的贡献为:
$$
g(x) = [x = 0] = \sum\limits_{i=0}^x {x \choose i} f(i+1)
$$
二项式反演得:
$$
\begin{aligned}
f(x + 1) &= \sum\limits_{i=0}^x (-1)^{x-i} {x \choose i} g(i) \\
\Rightarrow \ \ \ f(x + 1) &= (-1)^{x} \\
\Rightarrow \ \ \ f(x) &= (-1)^{x-1}
\end{aligned}
$$
所以:
$$
\begin{aligned}
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) f(|S’|) \\
&= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$