前置知识

$\min$-$\max$ 容斥, 离散型随机变量的几何分布,FMT 或者 FWT 之一.

思路

先将数在二进制下全部表示成集合, 设 $\min\{S\}$ 表示 $S$ 有至少一个元素变为 $1$ 的期望次数,$\max\{S\}$ 表示 $S$ 每个元素都变为 $1$ 的期望次数.

显然最后要求的是 $\min\{U\}$,$U$ 是全集, 但是看起来并没有那么好求. 试着用 $\min$-$\max$ 容斥, 需要求的是 $\min\{S\subseteq U\}$.

记 $f(S)$ 为某一次选择中选中 $S$ 的子集概率, 则

$$ \mathrm P(\min\{S\}=k)=f(\complement_S)^{k-1}(1-f(\complement_S)) $$

即 $\min\{S\}=k$ 意味着前 $k-1$ 次全部选到了 $S$ 的补集 $\complement_S$ 当中, 第 $k$ 次选到了 $S$ 当中的元素. 之所以是 $1-f(\complement_S)$ 而不是 $f(S)$ 是因为并不一定要全部选到 $S$ 当中, 一部分在 $S$ 内而一部分在 $S$ 外仍是合法情况, 即只要不全在 $\complement_S$ 中即可.

我们发现这个式子服从参数为 $1-f(\complement_S)$ 的几何分布, 所以

$$ \mathrm E(\min\{S\})=\frac 1{1-f(\complement_S)} $$

所以接下来要求的就是 $f(S)$. 我们记 $g(S)$ 为恰好选中 $S$ 的概率, 则显然有

$$ f(S)=\sum_{S\supseteq T}g(T) $$

这是一个集合并卷积, 可以用 FMT 来做, 但是不需要做逆变换. 当然 FWT 也能做, 但是比较麻烦所以窝没去看.

然后就照着容斥的式子套一遍就完了.

Code

另外那个SPJ是假的, 窝输出IOI KA ukiM_wonS会 WA 一个点.

#include <cstdio>
using namespace std;

const double eps=1e-8;

int main() {
    static int s[1048585];
    static double p[1048585];
    int n,m; double r=0;
    scanf("%d",&n); m=1<<n;
    for (int i=0;i<m;++i) {
        scanf("%lf",&p[i]);
        s[i]=s[i>>1]+(i&1);
    }
    for (int i=1;i<m;i<<=1) for (int j=0;j<m;j+=(i<<1))
        for (int k=0;k<i;++k) p[i+j+k]=p[i+j+k]+p[j+k];
    for (int i=1;i<m;++i) {
        if (1-p[(m-1)^i]<eps) {
            printf("INF");
            return 0;
        }
        s[i]&1?r+=1/(1-p[(m-1)^i]):r-=1/(1-p[(m-1)^i]);
    }
    printf("%.10lf",r);
    return 0;
}