min-max容斥学习笔记

min-max容斥(极值反演)

(min-max)容斥是说一个这样的式子：
[ max{S}=sum_{Tsubseteq S}(-1)^{|T|+1}min{T} ]

[ min{S}=sum_{Tsubseteq S}(-1)^{|T|+1}max{T} ]

其中(min{S})表示(S)集合中的最小元素，(max{S})表示最大元素。

---

第一个式子证明如下：

我们尝试着给式子配上一个容斥系数(f)，那么写出来就是：
[ max{S}=sum_{Tsubseteq S}f(|T|)min{T} ]
考虑第(x+1)大的元素被统计到的次数，我们可以枚举有多少个集合的最小值为第(x+1)大的元素，就是说我们只把前(x+1)个元素拿出来，可以得到：
[ res=sum_{i=1}^{x+1}binom{x}{i-1}f(i)=sum_{i=0}^{x}binom{x}{i}f(i+1) ]
那么我们现在只想把最大的容斥出来，有：
[ [x=0]=sum_{i=0}^{x}binom{x}{i}f(i+1) ]
二项式反演一下可得：
[ f(x+1)=sum_{i=0}^{x}(-1)^{x-i}binom{x}{i}[i=0] ]
注意这里是把左边当成了(g(x)=[x=0])。

那么化简就是：
[ f(x+1)=(-1)^x ]
即：
[ f(x)=(-1)^{x-1}=(-1)^{x+1} ]
证毕。

---

广义min-max容斥

这玩意说白了就是这个式子：
[ max_k(S)=sum_{Tsubseteq S}(-1)^{|T|+1}binom{|T|-1}{k-1}min(T) ]
其中(max_k(S))表示(S)集合中第(k)大的值是多少。

---

证明如下：

考虑我们还是想把它容斥出来，那么尝试着配个容斥系数(f(|T|))，则：
[ max_k(S)=sum_{Tsubseteq S}f(|T|)min(T) ]
同上，考虑第(x+1)大的元素被统计了多少次，可得：把式子抄过来
[ res=sum_{i=1}^{x+1}binom{x}{i-1}f(i)=sum_{i=0}^{x}binom{x}{i}f(i+1) ]
我们是想把第(k)大的容斥出来，其他的都不要，则：
[ sum_{i=0}^{x}binom{x}{i}f(i+1)=[x=k-1] ]
设后面的为(g(x)=[x=k-1])，二项式反演可得：
[ f(x+1)=sum_{i=0}^x(-1)^{x-i}binom{x}{i}g(i)=sum_{i=0}^x(-1)^{x-i}binom{x}{i}[i=k-1] ]
化简可得：
[ f(x+1)=(-1)^{x-k+1}binom{x}{k-1} ]
即：
[ f(x)=(-1)^{x-k}binom{x-1}{k-1} ]
得证。

---

看上面的感觉这玩意还是没有什么用，但是最有用的一点是这玩意在期望的意义下成立，即：
[ E(max{S})=sum_{Tsubseteq S}(-1)^{|T|+1}E(min{T}) ]

[ E(max_k(S))=sum_{Tsubseteq S}(-1)^{|T|+1}binom{|T|-1}{k-1}E(min(T)) ]

具体的应用可以看一下下面的习题。

习题

min-max容斥

[HDU4336]Card Collector，sol.

[BZOJ4036] [HAOI2015]按位或，sol.

[LOJ#2542] [PKUWC2018] 随机游走，sol.

广义min-max容斥

[luoguP4707] 重返现世，sol