记录编号	163761	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]按位或	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.631 s
提交时间	2015-05-25 21:06:17	内存使用	40.29 MiB

#include<cstdio>
using namespace std;
int n,cnt[1<<21];
double P[1<<21],F[1<<21],eps=1e-9;
int main()
{
	freopen("haoi2015_set.in","r",stdin);
	freopen("haoi2015_set.out","w",stdout);
	scanf("%d",&n);
	int N=1<<n;
	cnt[0]=0;
	for(int i=1;i<N;i++)
	cnt[i]=cnt[i>>1]+(i&1);
	for(int i=0;i<N;i++)
	scanf("%lf",&P[i]);
	for(int i=0;i<N;i++)
		F[i]=P[i];
	for(int i=0;i<n;i++)
		for(int s=0;s<N;s++)
			if((s>>i)&1) F[s]+=F[s^(1<<i)];
	double ans=0;
	for(int i=0;i<N-1;i++)
	{
		double p=F[i];
		if(1-p<eps) {printf("INF\n");return 0;}
		double now=1/(1-p);
		if((n-cnt[i])&1) ans+=now;
		else ans-=now;
	}
	printf("%.10lf",ans);
	return 0;
}