min-max容斥

· · 个人记录

可以忽略掉这一段

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

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

例题

参考资料