洛谷 P3175 [HAOI2015]按位或(FMT+minmax容斥)

题目链接

minmax容斥又称最值反演，是一种针对集合min->max或者max->min的反演

结论公式为

m a x { S } = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 m i n { T } max\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}min\{T\} max{S}=∑T⊆S​(−1)∣T∣+1min{T}

m i n { S } = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 m a x { T } min\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}max\{T\} min{S}=∑T⊆S​(−1)∣T∣+1max{T}

这个应该还蛮好证明的

我们考虑构造一个函数

m a x { S } = ∑ T ⊆ S F ( ∣ T ∣ ) m i n { T } max\{S\}=\sum_{T\subseteq S}F(|T|)min\{T\} max{S}=∑T⊆S​F(∣T∣)min{T}

那么分析一下第 x + 1 x+1 x+1大的数字会被枚举到几次

显然是从比他大的 x x x个里任意取出若干个与他构成集合，也就是 ∑ i = 0 x ( x i ) \sum_{i=0}^{x}{x\choose i} ∑i=0x​(ix​)个

然后他出现的次数应该是 ∑ i = 0 x ( x i ) f ( i + 1 ) \sum_{i=0}^{x}{x\choose i}f(i+1) ∑i=0x​(ix​)f(i+1)

显然只有第0大（最大）的才会出现次数是一，所以我们规定大函数 F ( x ) = [ x = = 0 ] F(x)=[x==0] F(x)=[x==0]

F ( x ) = ∑ i = 0 x ( x i ) f ( i + 1 ) F(x)=\sum_{i=0}^{x}{x\choose i}f(i+1) F(x)=∑i=0x​(ix​)f(i+1)

愉快的二项式反演一波

f ( x + 1 ) = ∑ i = 0 x ( − 1 ) x − i ( x i ) F ( i ) f(x+1)=\sum_{i=0}^{x}(-1)^{x-i}{x\choose i}F(i) f(x+1)=∑i=0x​(−1)x−i(ix​)F(i)

f ( x + 1 ) = ∑ i = 0 x ( − 1 ) x − i ( x i ) [ i = = 0 ] f(x+1)=\sum_{i=0}^{x}(-1)^{x-i}{x\choose i}[i==0] f(x+1)=∑i=0x​(−1)x−i(ix​)[i==0]

f ( x + 1 ) = ( − 1 ) x f(x+1)=(-1)^{x} f(x+1)=(−1)x

f ( x ) = ( − 1 ) x − 1 f(x)=(-1)^{x-1} f(x)=(−1)x−1

但其实 ( − 1 ) x − 1 (-1)^{x-1} (−1)x−1与 ( − 1 ) x + 1 (-1)^{x+1} (−1)x+1也没啥差别对吧，所以最值反演按照上面表述也是正确的。

同样的minmax容斥可以被扩展成这样子两个式子

l c m { S } = ∏ T ⊆ S g c d { T } lcm\{S\}=\prod_{T \subseteq S}gcd\{T\} lcm{S}=∏T⊆S​gcd{T}

E [ m a x { S } ] = ∑ T ⊆ S ( − 1 ) ∣ T ∣ + 1 E [ m i n { T } ] E[max\{S\}]=\sum_{T\subseteq S}(-1)^{|T|+1}E[min\{T\}] E[max{S}]=∑T⊆S​(−1)∣T∣+1E[min{T}]

这道题要用到的就是后者。

我们转化题意就是求全集中最后一个1出现的期望

用minmax容斥可以转化成集合中第一个1出现的期望

这个期望就是概率分之一，所以直接考虑概率

显然第一个1出现的概率就是1减去这个集合的补集的所有子集出现的概率和

子集和什么的FMT就可以达到正确复杂度了

那么这题就做完了

代码如下：

#include<bits/stdc++.h>
using namespace std;

int lim,n;
double p[1100000],ans;
int cnt[1100000];

int main()
{
	scanf("%d",&n);
	lim=1<<n;
	for(int i=0;i<lim;i++) scanf("%lf",&p[i]);
	for(int mid=1;mid<lim;mid<<=1)
	{
		for(int i=0;i<lim;i+=(mid<<1))
		{
			for(int j=0;j<mid;j++)
			{
				p[i+j+mid]+=p[i+j];
			}
		}
	}
	for(int i=1;i<lim;i++)
	{
		cnt[i]=cnt[i>>1]+(i&1);
	}
	for(int i=1;i<lim;i++)
	{
		if(1.0-p[(lim-1)^i]<1e-9)
		{
			puts("INF");
			return 0;
		}
		ans+=((cnt[i]&1)?1.0:-1.0)*(1.0/(1.0-p[(lim-1)^i]));
	}
	printf("%.6lf",ans);
}