min-max容斥

# 可以忽略掉这一段 之前写过一篇 [初探容斥原理](https://www.luogu.org/blog/KingSann/chu-tan-rong-chi-yuan-li)，评论里有这么一句：  然后我发现我并不会……于是就去学了一下 `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](http://acm.hdu.edu.cn/showproblem.php?pid=4336) [题解](https://www.luogu.org/blog/KingSann/hdu-4336card-collector) - [\[HAOI 2015\] 按位或](https://www.luogu.org/problemnew/show/P3175) [题解](https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p3175) - [\[51nod 1355\] 斐波那契的最小公倍数](https://www.51nod.com/Challenge/Problem.html#!#problemId=1355) [题解](https://www.luogu.org/blog/KingSann/post-51nod-1355-fei-bo-nei-qie-di-zui-xiao-gong-bei-shuo) - [\[洛谷 P4707\] 重返现世](https://www.luogu.org/problemnew/show/P4707) [题解](https://www.cnblogs.com/Trrui/p/9994668.html) - [\[Lydsy1704月赛\] 最小公倍佩尔数](https://www.lydsy.com/JudgeOnline/problem.php?id=4833) [题解](https://blog.csdn.net/qq_35649707/article/details/81170007) - [\[PKUWC2018\] 随机游走](https://loj.ac/problem/2542) [题解](https://www.luogu.org/blog/KingSann/pkuwc2018-sui-ji-you-zou) # 参考资料 - [Miskcoo 反演魔术：反演原理及二项式反演](http://blog.miskcoo.com/2015/12/inversion-magic-binomial-inversion) - [ez_2016gdgzoi471【Learning】min-max容斥以及推广](https://blog.csdn.net/ez_2016gdgzoi471/article/details/81416333)