题意
你有一个数 \(x\)，初始时 \(x=0\)，每次按照给定的概率选择一个 \(y\in[0,s^n-1]\)，把你 \(x\) 变成 \(x|y\)。问期望几次，能让 \(x\) 变成 \(2^n-1\)。
\(n\le20\)。
思路
设 \(\max(S)\) 表示 \(S\) 中最晚的那个位置出现的时间，\(\min(S)\) 表示 \(S\) 中最近的那个位置出现的时间。
根据 \(min-max\) 反演，有 \(\max(S)=\sum_{T\subseteq S,T\not=\emptyset}(-1)^{|T|+1}\min(T)\)，两边加上期望，变成 \(E(\max(S))=\sum_{T\subseteq S,T\not=\emptyset}(-1)^{|T|+1}E(\min(T))\)。考虑如何求 \(\min(S)\)。设选到和 \(S\) 有交集的数的概率和为 \(p\)，那么 \(\min(S)=p+(1-p)(\min(S)+1)\)，得 \(\min(S)=\frac 1p\)，而 \(p\) 可以用子集求和求出。
时间复杂度 \(\mathcal O(n2^n)\)。
代码
// Problem: P3175 [HAOI2015] 按位或
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3175
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=1100000;
int n;
double f[maxn];
signed main(){read(n);for(int i=0;i<(1<<n);i++) scanf("%lf",f+i);for(int j=0;j<n;j++) for(int i=0;i<(1<<n);i++) if(i&(1<<j)) f[i]+=f[i^(1<<j)];double ans=0;for(int i=1;i<(1<<n);i++){int sz=0,val=0;for(int j=0;j<n;j++) if(((1<<j)&i)==0) val+=(1<<j);else sz++;if(1-f[val]<1e-10){write("INF");return 0;}if(sz&1) ans+=1/(1-f[val]);else ans-=1/(1-f[val]);}if(isinf(ans)) write("INF");else printf("%.10lf",ans);return 0;
}