可以忽略掉这一段
之前写过一篇 初探容斥原理，评论里有这么一句：
然后我发现我并不会……于是就去学了一下 min-max容斥 ……
前置知识
二项式反演
$$ \begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned} $$
快速入门
设有一集合 $S$，定义 $\max(S)$ 表示集合 $S$ 的最大值，$\min(S)$ 表示集合 $S$ 的最小值
则有如下两个式子成立：
$$\begin{cases} &\max(S)=\sum\limits_{\emptyset \ne T \subseteq S}(-1)^{\mid T \mid + 1}\min(T) \\ &\min(S)=\sum\limits_{\emptyset \ne T \subseteq S}(-1)^{\mid T \mid + 1}\max(T) \end{cases}$$
证明的话其实十分简单易懂，在此只证明第一个的正确性
假设现在把集合 $S$ 从小到大排序（假设集合大小为 $x$），若某个元素的排名为 $x$，那么它在最终答案中的系数就是（考虑它在何时作为最小值出现）：
$$\sum_{i=0}^{n-x} {n-x \choose i} (-1)^{i+1+1}=(1-1)^{n-x}=[x=n]$$
于是一个元素对答案产生贡献当且仅当它是最大的元素，于是就是 $\max(S)$ 了
一个更加有用的结论是，min-max 容斥 在期望意义下仍然成立
也就是说：
$$\begin{cases} &E(\max(S))=\sum\limits_{\emptyset \ne T \subseteq S}(-1)^{\mid T \mid + 1}E(\min(T)) \\ &E(\min(S))=\sum\limits_{\emptyset \ne T \subseteq S}(-1)^{\mid T \mid + 1}E(\max(T)) \end{cases}$$
原理
那么这个是怎么推出来的呢……（注意这个很重要）
现在想构造一个 $f$ 函数，使得下式成立：
$$\max(S)=\sum_{T \subseteq S} f(\mid T \mid) \min(T)$$
然后依然考虑一个元素排序后在哪些集合产生贡献，假设某个元素从小到大后排在第 $x$ 位（集合大小为 $n$），那么它的贡献就是：
$$[x=n]=\sum_{i=0}^{n-x} {n-x \choose i}f(i+1)$$
套用二项式反演，可以得到：
$$[x=n]=\sum_{i=0}^{n-x} {n-x \choose i}f(i+1)$$
$$[n-x=0]=\sum_{i=0}^{n-x} {n-x \choose i} f(i+1)$$
$$[x=0]=\sum_{i=0}^{x} {x \choose i} f(i+1)$$
$$f(x+1)=\sum_{i=0}^{x}(-1)^{x-i} {x \choose i} [i=0]=(-1)^x {x \choose 0}=(-1)^{x}$$
$$f(x)=(-1)^{x+1}$$
于是就得到了：
$$\max(S)=\sum\limits_{\emptyset \ne T \subseteq S}(-1)^{\mid T \mid + 1}\min(T)$$
进阶
既然现在有了求最大值的容斥了，而且还知道原理，不放搞一搞第 $k$ 大的容斥
即现在要构造一个 $f$，满足：
$$kthmax(S)=\sum_{T \subseteq S} f(\mid T \mid) \min(T)$$
依然是考虑一个排名（从小到大）为 $x$ 的元素在大小为 $n$ 的集合中的贡献：
$$[n-x+1=k]=\sum_{i=0}^{n-x} {n-x \choose i} f(i+1)$$
$$[x=k-1]=\sum_{i=0}^{x} {x \choose i} f(i+1)$$
$$f(x+1)=\sum_{i=0}^{x} (-1)^{x-i} {x \choose i} [i=k-1]=(-1)^{x-(k-1)}{x \choose k-1}$$
$$f(x)=(-1)^{x-k} {x-1 \choose k-1}$$
也就是说：
$$kthmax(S)=\sum_{T \subseteq S} (-1)^{\mid T \mid-k} {\mid T \mid -1 \choose k-1} \min(T)$$
例题
- [hdu 4336] Card Collector 题解
- [HAOI 2015] 按位或 题解
- [51nod 1355] 斐波那契的最小公倍数 题解
- [洛谷 P4707] 重返现世 题解
- [Lydsy1704月赛] 最小公倍佩尔数 题解
- [PKUWC2018] 随机游走 题解
