min-max容斥略解

Part1:(min-max) 容斥的引入

我们设有一个全集(U={a_1,a_2,dots,a_n}),我们记(min S=minlimits_{a_iin S}a_i),(max S=maxlimits_{a_iin S}a_i),假设我们可以轻易地得到(min S),但很难求得(max S),此时,为求(S),我们就要引入(mathbf{min})-(mathbf{max})容斥.

我们有以下关系:

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

这个式子被称为(mathbf{min})-(mathbf{max})容斥公式.我们下面来证明这个结论.

假设(max S)具有形式

[max S=sum_{Tsubseteq S}f(|T|)min T ]

其中(f(k))是容斥系数.我们考虑(k+1)大的元素会被统计到的贡献,即那些子集的最小值会为第(k+1)的元素.则

[[x==0]=sum_{i=0}^k inom kicdot f(i+1) ]

二项式反演得

[f(k+1)=sum_{i=0}^k(-1)^{k-i}inom ki[i==0] ]

得到

[f(k+1)=(-1)^k ]

即

[f(k)=(-1)^{k-1} ]

综上,

[egin{align*} max S&=sum_{Tsubseteq S}fleft(|T| ight)min T\ &=sum_{Tsubseteq S}(-1)^{|T|-1}min T end{align*} ]

当然,也可以把式子中的(max)与(min)互换,得到(min-max)容斥的另一种形式:

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

证明类似.

另外,(min-max)容斥公式在期望意义下也成立.设全集(U={X_1,X_2,dots,X_n})是由两两不相关的随机变量构成的集合,并且其期望(E(X_1),E(X_2),dots,E(X_n))均存在,则

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

其中(E(max S))表示(S)中元素最大值的期望.注意,若(X,Y)不相关,则(E(max{X,Y}) e max{E(X),E(Y)}),所以期望意义下的最值是很难求的,而(min-max)容斥给了我们一个有力的工具.

举个栗子,假设有随机试验(E),样本空间为(S={0,1})(其意义可理解为抛硬币),(X=X(e),Y=Y(e))是这个样本空间上的两个不相关随机变量,易知(E(X)=E(Y)=1/2),那么令(Z=max(X,Y)),则(Z)的分布律为

[egin{array} {c|c|c|c|c|} X&max{0,0}&max{0,1}&max{1,0}&max{1,1}\ p&frac14&frac14&frac14&frac14 end{array} ]

因此(E(Z)=4/3).但(max{E(X),E(Y)}=0.5),所以期望与(max)/(min)是不相容的.

Part2:(kmathrm{th}min-max)容斥

我们要求第(k)大,怎么求呢?

我们仍然用上面的证明方法,假设其具有如下形式:

[kmathrm{th}max S=sum_{Tsubseteq S}f(|T|)min T ]

设一个元素(a)排名为第(m)大,那么有且只有不包含比它小的(n-m+1)个元素时,(min T=a).若有(m-1)个元素可供随意选择,那么必然选择(a).于是得

[[m=k]=sum_{i=1}^{m-1}inom{m-1}i f(i+1)Leftrightarrow\ [m=k-1]=sum_{i=1}^minom mi f(i+1) ]

二项式反演得

[f(m+1)=sum_{i=1}^m(-1)^{m-i}inom mi[i=k-1]=(-1)^{m-k+1}inom m{k-1} ]

所以

[f(m)=(-1)^{m-k}inom{m-1}{k-1} ]

因此,

[kmathrm{th}max S=sum_{Tsubseteq S}(-1)^{|T|-k}inom{|T|-1}{k-1}min T ]

同样的,

[kmathrm{th}min S=sum_{Tsubseteq S}(-1)^{|T|-k}inom{|T|-1}{k-1}max T ]

上述公式也对期望成立.

Part3:例题

LG P3175 [HAOI2015]按位或

由于或运算时每个位都是独立的,我们可以把每个位分开来看.我们设(a_k)为第(k)个为变为(1)的时间,那么我们要求的就是(E(max U))((U)为全集).

那么,怎么求(min S)((Ssubseteq U))呢?

为了方便,我们形式地记(P(S))为选中(S)子集的概率值和.那么,(min S=k)的概率就是,前(k-1)次选了(ar S)的子集,最后一次不选(ar S)子集的概率.于是得

[P{min S=k}=P(Soplus U)^{k-1}[1-P(Soplus U)] ]

其中(Soplus U)表示(S)与(U)的位运算卷积.我们可以发现(min S)服从参数为(1-P(Soplus U))的几何分布,那么,

[egin{align} E(min S)&=sum_{k=1}^{infty}kP{min S=k}\ &=sum_{k=1}^{infty }kP(Soplus U)^{k-1}[1-P(Soplus U)]\ &=frac1{1-P(Soplus U)} end{align} ]

易知(P(S)=sum_{Tsubseteq S}P{T ext{被选中}}),直接枚举子集求即可,然后再用或运算的离散沃尔什变换求即可.时间复杂度(O(ncdot 2^n)).

C++实现如下:

int n,lim;
double p[(1<<20)+5],ans;

int main()
{
	scanf("%d",&n);
	lim=1<<n;

	for(int i=0;i<=lim-1;++i)
		scanf("%lf",p+i);
		
	for(int i= 1;i<lim;i<<=1)
		for(int j=0;j<lim;j+=i<<1) 
			for(int k=0;k<=i-1;++k)
				p[i+j+k]+=p[j+k];
				
	for(int i=1;i<=lim-1;++i)
	{
		double q=1-p[(lim-1)^i];
		
		if(q<=1e-10)
		{
			puts("INF");
			return 0;
		}
		
		ans+=(__builtin_popcount(i)&1?1:-1)*1.0/q;
	}
	
	printf("%.10lf
",ans);
}

LG P4707重返现世

我们设集合(S)为某些物品的集合,物品的权值为第一次出现的时间.那么,(E(min S))就是这些物品中有任意一个出现的期望时间.

若每一次得到(S)中物品的概率为(sumlimits_{iin S}p_i),那么期望的时间就是(1/sumlimits_{iin S}p_i).

(E(min S))是显然易求的.我们再来考虑题目要求的(kmathrm{th}min U).

通过(min-max)容斥易知

[ans=sum_{Tsubseteq S}(-1)^{|T|-k}inom{|T|-1}{k-1}E(min T) ]

观察和式,变量有且只有(|T|),(E(min T)),同时(E(min T)=sumlimits_{iin T}p_i).

我们设(f(i,j,k))为前(i)选了(j)个时(sumlimits_{iin T}p_i=k)的方案数.最后只需把方案数求和再乘以对应权值,求和既得答案.转移方程是易得的:

[f(i,j+1,k+p_i)Leftarrow f(i,j+1,k+p_i)+f(i-1,j-k) ext{选当前物品}\ f(i,j,k)Leftarrow f(i,j,k)+f(i-1,j,k) ext{不选当前物品} ]

可以考虑使用滚动数组压缩第一维空间.复杂度(O(n^2m)),可得70分.

我们考虑满分做法.可以发现每个项的贡献(=E(min T)cdot ext{与}|T| ext{相关的项}cdot ext{方案数}).我们考虑一个技巧:把维数藏在权值里.就是直接把这个式子的一部分作为权值,以减少维数.但是降维之后,由于我们把未知量强行加入了dp的权值之中,所以我们还要在状态上附加一个维数.

观察数据范围,(kle 11),那么这个新的维度就很有可能是(k)了.设(f(i,j))表示前(i)个物品,(sumlimits_{iin T}p_i=j)的((-1)^{|T|-k}inom{|T|-1}{k-1})之和.转移方程如下:

[f(i,j)Leftarrow f(i,j)+f(i-1,j) ext{不选当前物品}\ f(i,j+p_i)=? ext{选当前物品} ]

我们尝试求选物品时的转移方程.可以得到,(sum(-1)^{|T|-k}inom{|T|-1}{k-1})在加入了一个元素之后就变成(sum(-1)^{|T|-k+1}inom{|T|}{k-1}).将组合数拆开,得到

[(-1)^{|T|-k+1}inom{|T|}{k-1}=(-1)^{|T|-k+1}left[inom{|T|}{k-2}+inom{|T|-1}{k-1} ight] ]

于是原式就等价于

[sum(-1)^{|T|-k-1}inom{|T|}{k-2}-sum(-1)^{|T|-k}inom{|T|-1}{k-1} ]

减数就等于(f(i-1,j)).于是我们得到了正解:

设(f(i,j,k))表示前(i)个物品,(sum_{iin T}p_i=j)且(k)如所设的((-1)^{|T|-k}inom{|T|-1}{k-1})的和.根据上面的推导,有

[f(i,j,k)Leftarrow f(i,j,k)+f(i-1,j,k) ext{不选当前物品}\ f(i,j+p_i,k)Leftarrow f(i-1,j,k-1)-f(i-1,j,k) ext{选当前物品} ]

边界条件(f(0,0,0)=1).仍使用滚动数组压缩第一维.注意有(p_i=0)的情况.