可以忽略掉这一段

之前写过一篇 初探容斥原理,评论里有这么一句:

然后我发现我并不会……于是就去学了一下 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)$$

例题

参考资料