洛谷 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);
}