【BZOJ4036】[HAOI2015]按位或

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

题解：先判无解。然后进行fwt。对于每一项p，一次操作变成p的概率是$p$，两次是$p^2$，三次是$p^3$...所以期望次数就是$p\over (p-1)$。特别地，$2^n-1$的p=1，因为它不需要操作所以次数为0。再fwt回去即可。

手写小数读入优化炸精度调了半个小时~再也不写小数读入优化了~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef double db;

const int maxn=(1<<20)+4;

const db eps=1e-7;

db f[maxn],g[maxn];

bool vis[30];

int n;

db rd()

{

	db ret=0,tmp=0.1;	char gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	if(gc=='.')

	{

		gc=getchar();

		while(gc>='0'&&gc<='9')	ret=ret+(gc-'0')*tmp,tmp/=10,gc=getchar();

	}

	return ret;

}

inline void fwt(db *a)

{

	int i,h;

	for(h=0;h<n;h++)	for(i=0;i<(1<<n);i++)	if((i>>h)&1)	a[i]+=a[i^(1<<h)];

}

inline void ufwt(db *a)

{

	int i,h;

	for(h=0;h<n;h++)	for(i=0;i<(1<<n);i++)	if((i>>h)&1)	a[i]-=a[i^(1<<h)];

}

int main()

{

	n=rd();

	int i,j;

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

	{

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

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

	}

	for(j=0;j<n;j++)	if(!vis[j])

	{

		puts("INF");

		return 0;

	}

	fwt(f);

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

	{

		if(i==(1<<n)-1)	f[i]=0;

		else	f[i]=f[i]/(f[i]-1);

	}

	ufwt(f);

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

	return 0;

}//2 0.25 0.25 0.25 0.25

巴特西

【BZOJ4036】[HAOI2015]按位或 FWT