P3175 [HAOI2015]按位或

传送门

一如既往膜拜shadowice巨巨

前置姿势我就没一个会的……

//minamoto
#include<bits/stdc++.h>
#define R register
#define eps 1e-10
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=(1<<20)+5;
double a[N],res;int n,lim,sz[N];
int main(){
//freopen("testdata.in","r",stdin);
scanf("%d",&n);lim=1<<n;fp(i,0,lim-1)scanf("%lf",&a[i]);
for(R int mid=1;mid<lim;mid<<=1)
for(R int j=0;j<lim;j+=(mid<<1))
for(R int k=0;k<mid;++k)
a[j+k+mid]+=a[j+k];
fp(i,1,lim-1)sz[i]=sz[i>>1]+(i&1);
fp(i,1,lim-1){
if(1-a[(lim-1)^i]<eps)return puts("INF"),0;
res+=1/(1-a[(lim-1)^i])*(sz[i]&1?1:-1);
}printf("%.10lf\n",res);return 0;
}