[HAOI2015]按位或（FWT）

我们要求的，实际上是一个集合\(n\)个\(1\)中最晚出现的\(1\)的期望时间

显然\(minmax\)容斥

\(E(max\{S\})=∑_{T⊆S}(−1)^{|T|+1}E(min\{T\})\)

那么问题就转化为了求每个集合中最早出现的\(1\)的期望时间

假如在\(k\)时刻出现，那么前\(k−1\)时刻一定都是取的补集的子集，记\(T\)补集的所有子集概率和为\(P\)

\(E(min\{T\})=∑_{k=1}^{∞}kP(1−P)^{k−1}\)

是一个离散变量的几何分布

设\(P(x=a)=p\)

那么取到\(a\)的期望为

\(E(x=a)=∑_{k=1}^{∞}k(1−p)^{k−1}p=p∑_{k=1}^{∞}k(1−p)^{k−1}\)

记\(f(x)=1+2x+3x^2+4x^3+…\)

则\(xf(x)=x+2x^2+3x^3+4x^4+…\)

则\((1−x)f(x)=1+x+x^2+x^3+…\)

对于\(0<x<1，(1−x)f(x)\)是收敛的，可以取到

\((1−x)f(x)=\frac{1}{1−x}\)

\(f(x)=\frac{1}{(1−x)^2}\)

所以

\(E(x=a)=p\frac{1}{p^2}=\frac{1}{p}\)

非常棒

于是有

\(E(min{T})=\frac{1}{1−P}\)

我们只需要求出所有集合的子集概率和就好了

其实就是或运算的\(FWT\)

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

	register LL x=0,f=1;register char c=getchar();

	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

	while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

	return f*x;

}

const int MAXN=1<<20;

const double eps=1e-8;

double f[MAXN],ans;

int bit[MAXN],n,len;

int main(){

	n=read();len=1<<n;

	for(int i=0;i<len;i++) scanf("%lf",&f[i]);

	for(int i=2;i<=len;i<<=1){

		for(int j=0,p=i>>1;j<len;j+=i)

			for(int k=j;k<j+p;k++)

				f[k+p]+=f[k];//这里的特殊写法有助于理解FWT,FFT系列操作

	}

	for(int i=0;i<len;i++) bit[i]=bit[i>>1]+(i&1);

	for(int i=1;i<len;i++){

		double tmp=(1-f[(len-1)^i]);

		if(tmp<eps){printf("INF\n");return 0;}

		if(bit[i]&1) ans+=1.0/tmp;

		else ans-=1.0/tmp;

	}

	printf("%.8lf\n",ans);

}

巴特西

[HAOI2015]按位或（FWT）

\(E(max\{S\})=∑_{T⊆S}(−1)^{|T|+1}E(min\{T\})\)

最新文章

热门文章