浅谈min-max容斥

基础min-max容斥

min-max容斥是一种用集合的min来表示集合的max的方法。
对于一个集合S,令$max(S)$为$S$中的最大元素,$min(S)$为$S$中的最小元素。
比如对于一个两个元素的集合$S={a,b}$,显然$max(S)=min({a})+min({b})-min({a,b})$
更普遍地,有如下性质:
$$max(S)=\displaystyle\sum_{T\subseteq S,T\not =\varnothing} min(T) (-1)^{|T|-1}$$
证明非常简单,我们考虑每一个元素出现的次数,第x大的被统计的次数:$\sum_{i=0}^{x-1} C_{x-1}^i (-1)^{i}=[x==1]$
所以这个是对的。
那么这个结论有什么用呢?主要是对于一些具有线性性的问题我们可以用这个式子对min和max进行转换。

例题 hdu4336 Card Collector

题目大意:有n种元素,每个时刻会出现一种元素,第i个元素出现的概率是$p_i$,如果某一个时刻你还没有出现的这种元素,就可以收集这一种元素。求收集所有元素的期望时间。
$n\le 20$,多组数据
如果直接dp,复杂度是$O(2^n\times n)$的,但是min-max容斥可以做到$O(2^n)$
期望具有线性性,所以有:
$$E(max(S))=\displaystyle\sum_{T\subseteq S,T\not =\varnothing} E(min(T)) (-1)^{|T|-1}$$
那我们怎么把这个问题转化为集合的问题的?
不妨令$E(max(S))$为集合$S$中出现时间最晚的元素的出现时间。$min(S)$同理。
显然我们要求的是这个集合的最大值的期望,这个我们直接很难求。但是这个集合的最小值的期望很好求,$E(min(T))=\frac{1}{\displaystyle\sum_{i\in T} p_i}$
所以这个直接套min-max容斥就好了。

kth min-max容斥

令$max(k,S)$为S集合中第k大的元素($|S|\ge k$),我们依然可以使用集合的$min$来将其表示出。
和之前的情况相同,我们希望得到一个形如这样的一个式子:
$$max(k,S)=\displaystyle\sum_{T\subseteq S,T\not =\varnothing} f(k,|T|) min(T)$$
依然考虑每个元素的贡献,那么我们希望:
$$\displaystyle\sum_{i=0}^{x-1} C_{x-1}^i f(k,i+1)=[x=k]$$
关键是我们想知道如果构造出一个$f$使得该式子成立。
考虑之前的形式,我们现在需要一段类似于组合数的东西加上奇数的部分,减掉偶数的部分。
$C_{x-1}^i=\frac{(x-1)!}{(x-1-i)!i!}$,我们发现f只能与k和i有关,不能去消带x的项。
另外这里变量是i,也就是说我们需要一个$\frac{1}{(a-i)!(i-(k-1))!}$的形式,并且我们要消掉$i!$。
我们发现这个a已经存在了,就是(x-1),那么我们只需要消掉$i!$然后加入$\frac{1}{(i-(k-1))!}$这一项即可。
所以我们可以乘上$\frac{i!}{(i-(k-1))!}(-1)^{i-(k-1)}$,然后我们发现当$x-1\not =k-1$时这个是0了,但是当$x-1=k-1$时,它的结果是$(x-1)!$,所以我们干脆再除掉$(k-1)!$,那么$f(k,i+1)=\frac{i!}{(i-k+1)!(k-1)!}(-1)^{i-k+1}=C_{i}^{k-1}(-1)^{i-k+1}$,也就是$f(k,i)=C_{i-1}^{k-1}(-1)^{i-k}$
所以这个结果已经出来了:
$$max(k,S)=\displaystyle\sum_{T\subseteq S,T\not =\varnothing} C_{|T|-1}^{k-1}(-1)^{|T|-k} min(T)$$
我们发现当$k=1$是这个式子就是原来的min-max容斥的式子。

例题:洛谷P4707 重返现世

这道题是kth min-max容斥的经典题。
题目大意(略有改变):有n种元素,每个时刻会出现一种元素,第i个元素出现的概率是$\frac{p_i}{m}$($p_i$是非负整数,$\sum p_i=m$),求收集恰好$n-k$个元素的期望时间
$n\le 1000,m\le 10000,k\le 10$
类似地,我们的答案为:
$$\displaystyle\sum_{T\subseteq \lbrace 1,2,…,n\rbrace,T\not =\varnothing} C_{|T|-1}^{k-1}(-1)^{|T|-k} \frac{m}{\sum_{i\in T} p_i}$$
我们考虑dp,令:
$$f(i,j,t)= \displaystyle\sum_{T\subseteq \lbrace 1,2,…,i\rbrace,T\not =\varnothing} C_{|T|-1}^{t-1}(-1)^{|T|-t} m [\sum_{e\in T} p_e=j]$$
由于$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
所以有:$f(i,j,t)=f(i-1,j,t)-f(i-1,j-p_i,t)+f(i-1,j-p_i,t-1)$
直接按通项公式暴力算边界,然后按照递推式转移,处理完这个数组之后想怎么办就怎么办了。
答案就是$\displaystyle\sum_{j=1}^m \frac{f(n,j,k)}{j}$
时间复杂度$O(nmk)$,直接写会卡空间,要滚动掉一维。

Tagged with:

发表评论