【bzoj4036】[HAOI2015]按位或 fmt+期望

Description

刚开始你有一个数字0，每一秒钟你会随机选择一个[0,2^n-1]的数字，与你手上的数字进行或（c++,c的|,pascal

的or）操作。选择数字i的概率是p[i]。保证0<=p[i]<=1，Σp[i]=1问期望多少秒后，你手上的数字变成2^n-1。

Input

第一行输入n表示n个元素，第二行输入2^n个数，第i个数表示选到i-1的概率

Output

仅输出一个数表示答案，绝对误差或相对误差不超过1e-6即可算通过。如果无解则要输出INF

Sample Input

2

0.25 0.25 0.25 0.25

Sample Output

2.6666666667

HINT

对于100%的数据，n<=20

Sol

快速莫比乌斯变换和快速莫比乌斯逆变换自行百度。

设\(h(U)=\)最终答案，\(f_i(S)\)表示进行i次变换之后集合为\(S\)的概率，那么显然：

\(h(U)=\sum_{i=1}^{\infty}i*(f_i(U)-f_{i-1}(U))\)

设\(F_i(S)\)为\(f_i(s)\)的莫比乌斯变换，观察\(f_i(S)\)的定义，我们可以得到\(F_i(S)\)的式子：

\(F_i(S)=\sum_{s_1\in U}f_{i-1}(S_1)*\sum_{s_2\in U}f_1(S_2)\)

那么\(F_i(U)=(F_1(U))^i\)

所以\(H(U)=\sum_{i=1}^{\infty}i*((F_1(U))^i-(F_1(U))^{i-1})\)

\(-H(U)=\sum_{i=1}^{\infty}(F_1(U))^i\)

显然右边是一个等比数列求和的形式，而且数列的第\(\infty\)项是0，所以：

\(H(S)=\frac{F_1(S)}{F_1(S)-1}\)

然后就可以直接算了。注意全集的H是1。

Code

#include <bits/stdc++.h>

using namespace std;

int n,vis[1048577];double f[1048577];

void fmt(double *a){for(int k=0;k<n;k++) for(int i=0;i<(1<<n);i++) if((i>>k)&1) a[i]+=a[i^(1<<k)];}

void ufmt(double *a){for(int k=0;k<n;k++) for(int i=0;i<(1<<n);i++) if((i>>k)&1) a[i]-=a[i^(1<<k)];}

int main()

{

	scanf("%d",&n);

	for(int i=0;i<(1<<n);i++)

	{

		scanf("%lf",&f[i]);

		if(f[i]>0) for(int j=0;j<n;j++) if((i>>j)&1) vis[j]=1;

	}

	for(int i=0;i<n;i++) if(!vis[i]) return puts("INF"),0;

	fmt(f);

	for(int i=0;i<(1<<n);i++) f[i]=(i==((1<<n)-1))?1:f[i]/(f[i]-1);

	ufmt(f);

	printf("%.10lf\n",f[(1<<n)-1]);

}

巴特西