Description

Initially, you have the number $0$. Every second, you randomly choose a number from $[0,2^n-1]$ and apply bitwise OR with your current number (C++, C: |, Pascal: or). The probability of choosing number $i$ is $p_i$. It is guaranteed that $0\leq p_i \leq 1$, $\sum p_i=1$. Find the expected number of seconds until your current number becomes $2^n-1$.

Input Format

The first line contains $n$, the number of elements. The second line contains $2^n$ numbers; the $i$-th number is the probability of selecting $i-1$.

Output Format

Output a single number representing the answer. An absolute or relative error not exceeding $10^{-6}$ is accepted. If there is no solution, output INF.

2
0.25 0.25 0.25 0.25

2.6666666667

Hint

For $100\%$ of the testdata, $n\leq 20$.

The following is the SPJ source code.

//liuchenrui 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#define AC {fclose(fstd),fclose(fuser);return 0;}
#define WA {fclose(fstd),fclose(fuser);return 1;}
#define PE {fclose(fstd),fclose(fuser);return 5;}
#define eps 1e-6
int main(int const argc, char*const argv[]){
    FILE *fstd,*fuser;
    fstd=fopen(argv[2],"r");
    fuser=fopen(argv[3],"r");
    //fstd=fopen("x1.in","r");
    //fuser=fopen("x2.in","r");
    char s[30],t[30];
    if(fscanf(fuser,"%s",s+1)==-1)WA;
    fscanf(fstd,"%s",t+1);
    if(s[1]=='I' && t[1]=='I')AC;
    if(s[1]=='I' || t[1]=='I')WA;
    double p,q;
    sscanf(s+1,"%lf",&p);
    sscanf(t+1,"%lf",&q);
    if(fabs(p-q)<eps)AC
    else{
        if(fabs(p-q)/q<eps)AC;
        if(fabs(q-p)/q<eps)AC;
        if(fabs(p-q)/p<eps)AC;
        if(fabs(q-p)/p<eps)AC;
    }
    WA;
}

Translated by ChatGPT 5