题意
有一个初始为 \(0\) 的变量 \(x\)，每次操作会以 \(p_i\) 的概率选择位于 \([0,2^n)\) 中的某个整数 \(i\)，并将 \(x\) 或上 \(i\)。问期望几次操作后 \(x=2^n-1\)。
\(n\le 20,\sum p_i=1\)
引入：min-max 容斥
以两个式子入手：
\[\max(S)=\sum_{T\subseteq S} (-1)^{|T|+1}\min(T) \]\[\min(S)=\sum_{T\subseteq S} (-1)^{|T|+1}\max(T) \]两个式子的证明都大差不差，不妨证明第一个。
令 \(S=\{a_1,a_2,\cdots,a_n\}\)，其中 \(a_1<a_2<\cdots<a_n\)，考虑拆贡献，求出每个 \(a_i\) 对 \(\max(S)\) 的贡献的系数是多少。
不妨钦定 \(a_i\) 就是 \(\min(T)\)，那么 \(a_i\) 往后的元素都可以任意选，那 \(a_i\) 的系数就是 \(\sum_{j=0}^{n-i}(-1)^j\binom{n-i}{j}\)，这里是 \((-1)^j\) 不是 \((-1)^{j+1}\) 的原因是我们已经钦定 \(a_i\) 选了，所以少乘一个 \(-1\) 的系数。二项式定理可得 \(\sum_{j=0}^{n-i}(-1)^j\binom{n-i}{j}=(1-1)^{n-i}=[n=i]\)。也就是说，如果 \(a_i\) 不是 \(a_n\) 那么系数为 0，否则为 1。\(a_n\) 即是最大值，得证。
这个东西在一般的求最小值的题目下可能没啥用，但是这个东西在期望的意义下也是成立的（期望的线性性），即：
\[E(\max(S))=\sum_{T\subseteq S} (-1)^{|T|+1}E(\min(T)) \]\[E(\min(S))=\sum_{T\subseteq S} (-1)^{|T|+1}E(\max(T)) \]当 \(E(\max)\) 或 \(E(\min)\) 不好求且另外一个相对好求时，我们可以使用 min-max 容斥解决题目。
分析
将 \(x\) 拆位，设 \(t_i\) 表示第 \(i\) 位变成 1 的时刻，那么我们要求的就是 \(E(\max(t_i))\)。
考虑 min-max 容斥，将式子变为 \(\sum_{T\subseteq \{1,2,\cdots,n\},T\neq \emptyset} E(\min(T))\)。
我们有结论：设 \(p\) 表示选中与 \(T\) 有交的数的概率，那么有 \(E=\frac{1}{p}\)。
证明：
将期望按照定义展开，\(E=p(1-p)^0+2p(1-p)^1+3p(1-p)^2+\cdots\)，考虑错位相减，\((1-p)E=p(1-p)^1+2p(1-p)^2+3p(1-p)^3+\cdots\)，相减得 \(pE=p(1-p)^0+p(1-p)^1+p(1-p)^2+\cdots\)，也即 \(E=(1-p)^0+(1-p)^1+(1-p)^2+\cdots\)，套用等比数列求和公式得 \(E=\frac{1}{p}\)。
当然也有另外一种证法，考虑 DP，将 \(E\) 视为一个 DP 状态，有转移 \(E=1+(1-p)E\)，意义就是，我花费了一次操作，如果随到了与 \(T\) 有交的数（概率为 \(p\)），就结束了，否则要继续操作，此时局面和操作前一样，所以从 \((1-p)E\) 转移来。解方程得 \(E=\frac{1}{p}\)。
问题转化成了求 \(p\)。正着做稍微有点困难，考虑求选中与 \(T\) 无交的数的概率，即 \(1-p\)，不难发现这其实就是 \(T\) 的补集的所有子集的概率之和，高维前缀和即可。
还有一个小细节，当 \(p=0\) 时，此时 \(\frac{1}{p}\) 等于无穷大，所以要再开一个数组 \(cnt\) 记录 \(\frac{1}{0}\) 的系数是多少，若不为 0 则输出 INF。
时间复杂度 \(O(n2^n)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<array>
#include<ctime>
#include<random>
#include<cassert>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline void ckmx(T1 &x,T2 y){x=x>y?x:y;}
template<typename T1,typename T2>inline void ckmn(T1 &x,T2 y){x=x<y?x:y;}
inline auto rd(){
int qwqx=0,qwqf=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')qwqf=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+ch-48;ch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char ch='\n'){
if(qwqx<0){qwqx=-qwqx;putchar('-');}
int qwqy=0;char qwqz[40];
while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}
while(qwqy--)putchar(qwqz[qwqy]);if(ch)putchar(ch);
}
bool Mbg;
const int maxn=21,maxm=(1<<20),inf=0x3f3f3f3f;
const double eps=1e-10;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m;
double a[maxm],f[maxm];
inline void solve_the_problem(){
n=rd(),m=(1<<n);
rep(i,0,m-1)scanf("%lf",&a[i]);
rep(i,0,m-1)f[i]=a[i];
rep(j,0,n-1)rep(i,0,m-1)if((i>>j)&1)f[i]+=f[i^(1<<j)];
double ans=0;
int cnt=0;
rep(S,1,m-1){
double p=1-f[(m-1)^S];
int siz=__builtin_popcount(S);
if(p<eps){
if(siz&1)++cnt;
else --cnt;
}else{
if(siz&1)ans+=1.0/p;
else ans-=1.0/p;
}
}
if(cnt)puts("INF");
else printf("%.9lf",ans);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;
while(_--)solve_the_problem();
}
/*
*/