首先我们不能一位一位的考虑，为什么呢？
你想想，你如果一位一位地考虑的话，那么最后就只有 $n$ 个数字，然而他给了你 $2^n$ 个数字，怎么看都不对劲呀。（我是因为这样子弄没过样例才明白的）
所以我们还是要想想其他的方法。
我们是要算步数的期望，然而步数是一个离散的整数，所以我们可以把问题转化一下：
$$E(s) = \sum_{k=1}^{\infty}P(s\ge k)$$
然后就好做了嘛。
我们可以求出一个 $F_i = \sum_{j\subseteq i} p_j$，表示随机选一个数是 $i$ 的子集的概率。
那么就会有：
$$P(s\ge k) = \sum_{i=0}^{2^n-1}(-1)^{c(i)+n+1}\times F_i^{k-1}$$
其中 $c(i)$ 表示 $i$ 的二进制表示中 $1$ 的个数。以上的式子也就是一个容斥的样子，其实说起来就是位运算卷积。然后于是就有：
$$E(s) = \sum_{i=0}^{2^n-1} (-1)^{c(i)+n+1}\sum_{k=0}^{\infty}F_i^{k-1} = \sum_{i=0}^{2^n-1} \frac{(-1)^{c(i)+n+1}}{1 - F_i}$$
然后好像就做完啦。
时间复杂度 $O(n\times2^n)$，空间复杂度 $O(2^n)$。
#include <cstdio>
typedef long double LD;
#define N 1 << 20
#define eps 1e-11 int n, Op[N];
LD A[N]; int main()
{
scanf("%d", &n);
Op[] = n & ? : -;
for (int i = ; i < ( << n); i ++)
{
double x;
scanf("%lf", &x);
A[i] = x;
if (i > ) Op[i] = -Op[i - (i & -i)];
}
for (int k = ; k < ( << n); k <<= )
for (int i = ; i < ( << n); i ++)
{
if (i & k) continue ;
A[i + k] += A[i];
}
bool ok = ;
for (int i = ; ok && i < ( << n) - ; i ++)
if (A[i] + eps > ) ok = ;
if (!ok) puts("INF");
else
{
LD ans = ;
for (int i = ; i < ( << n) - ; i ++)
ans += Op[i] / ( - A[i]);
printf("%.10lf\n", (double) ans);
} return ;
}
4036_Gromah