题目概述
刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变成 $2^n-1$ 的期望时间。
解题报告
VFK的FMT论文题，先来讲下（抄下论文）FMT：
全集 $U=\{1,2,\cdots,n\}$ ，令 $2^U$ 表示 $U$ 的子集。定义集合幂级数 $f$ 是定义域在 $x\subseteq2^U$ （ $x$ 是集合）上的函数，$f=\sum_{s\subseteq2^U}f_sx^s$ ，其中 $x^s$ 只是一个符号，表示 $s$ 这个项，$f_s$ 是 $s$ 这个项的系数。
定义集合幂级数的加法运算是每项系数加起来，定义集合幂级数的乘法运算：
$$ f*g=\sum_{s\subseteq2^U}f_sx^s*\sum_{s\subseteq2^U}g_sx^s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}f_Ax^Ag_Bx^B=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}f_Ag_Bx^{A*B} $$
其中这个 $*$ 是个运算，想要满足上述式子这个 $*$ 就必须满足交换律，结合律，并且有单位元（空集 $\emptyset$ ），比如 $\cup$ 就是个满足的运算，接下来就用 $\cup$ 来看看。
$$ h=f*g=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}f_Ag_Bx^{A\cup B}\\ \Leftrightarrow h_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\cup B=s]f_Ag_B $$
直接做是 $O(4^n)$ 的，很难承受，所以要用到莫比乌斯变换和反演（这就是你叫FMT的理由？？？）：
令 $\hat{f}_A=\sum_{s\subseteq A}f_s$ ，那么根据容斥原理可以得出：$f_A=\sum_{s\subseteq A}(-1)^{|U|-|s|}\hat{f}_s$（集合加来减去那一套）。
听说这货在广义上和数论里的莫比乌斯反演是一样的？？？（只是听说，错了不要捶我QAQ）
这样的话我们对上面的式子两边变换：
$$ \hat{h}_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\cup B\subseteq s]f_Ag_B\\ \hat{h}_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\subseteq s]f_A[B\subseteq s]g_B\\ \hat{h}_s=\sum_{A\subseteq2^U}[A\subseteq s]f_A\sum_{B\subseteq2^U}[B\subseteq s]g_B\\ \hat{h}_s=\sum_{A\subseteq s}f_A\sum_{B\subseteq s}g_B\\ \hat{h}_s=\hat{f}_s\hat{g}_s $$
你没看错他最后就mogical了……可以直接乘起来啦。
问题是怎么实现莫比乌斯变换和反演，其实变换就是个子集求和，直接上高维前缀和，反演好像就比较奇怪，但是实际上你只要把高维前缀和代码里的 $+$ 改成 $-$ 就好了，因为高维前缀和每次增加一维，增加了之后符号就变了，所以把 $+$ 改成 $-$ 就自动实现了容斥的过程。
这样就可以把复杂度降到 $O(n2^n)$ 了。
然后对于这题，把读进来的 $2^n$ 个数当成集合幂级数 $p$ ，乘法是 $\cup$ 。那么可以得到答案的集合幂级数 $f$ ：
$$ f_s=\sum_{k=0}^{+\infty}k(p^{k}_s-p^{k-1}_s)\\ \hat{f}_s=\sum_{k=0}^{+\infty}k(\hat{p}^{k}_s-\hat{p}^{k-1}_s) $$
显然先变换再相减和先相减再变换是等价的，所以上述式子成立。然后开始处理上面的式子，我推了好久以为是什么神仙公式，结果发现这tm就是全列出来之后两项之间消掉变成：
$$ \hat{f}_s=\sum_{k=0}^{+\infty}-\hat{p}^k_s=-\sum_{k=0}^{+\infty}(\hat{p}_s)^k $$
无穷等比数列求和，得到 $\hat{f}_s={1\over\hat{p}_s-1}$ ，注意 $\hat{p}_s=1$ 的时候要特判 $\hat{f}_s=0$ 。最后反演得到 $f$ ，$f_U$ 就是答案。
示例程序
说了这么多，代码其实就是高维前缀和……
#include<cmath>
#include<cstdio>
using namespace std;
typedef double DB;
const int maxn=20,maxs=1<<maxn;
int n;DB p[maxs],f[maxs];
inline void FMT(DB *a,int n,int f){
for (int i=0;i<n;i++)
for (int j=0;j<(1<<n);j++)
if (j>>i&1) f>0?a[j]+=a[j^(1<<i)]:a[j]-=a[j^(1<<i)];
}
inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-10) return 0;return a<b?-1:1;}
int main(){
freopen("program.in","r",stdin);freopen("program.out","w",stdout);
scanf("%d",&n);for (int i=0;i<(1<<n);i++) scanf("%lf",&p[i]);FMT(p,n,1);
for (int i=0;i<(1<<n);i++) if (fcmp(p[i],1)<0) f[i]=1/(p[i]-1); else f[i]=0;FMT(f,n,-1);
if (!fcmp(f[(1<<n)-1],0)) puts("INF"); else printf("%.10f\n",f[(1<<n)-1]);return 0;
}
