Luogu

分析

我们把每个数看成一些二进制位的集合，每一位的值是加入的时间。那么我们要求的是全集的 $\max$ 值。

考虑 min-max 容斥
$$
E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(\min(T))
$$
$E(\min(S))$ 是好求的
$$
E(\min(S))=\frac{1}{\sum_{T\cap S\neq \varnothing}p_T}
$$
分母可以容斥一下
$$
\begin{aligned}
\sum\limits_{T\cap S\neq\varnothing}p_T & = 1 - \sum\limits_{T\cap S=\varnothing}p_T \\
& = 1 - \sum\limits_{T\subseteq\complement_TS}p_T
\end{aligned}
$$
那么只需要求子集和，可以 FMT。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define popcount __builtin_popcount
using namespace std;

const int N=1<<20;

double p[N];

int main() {
    int n; scanf("%d",&n); n=1<<n;
    for (re int i=0;i<n;++i) scanf("%lf",&p[i]);
    for (re int i=1;i<n;i<<=1)
        for (re int j=0;j<n;j+=(i<<1))
            for (re int k=0;k<i;++k)
                p[j+k+i]+=p[j+k];
    double ans=0;
    for (re int S=1;S<n;++S) {
        if (1-p[(n-1)^S]<1e-8) { puts("INF"); return 0; }
        if (popcount(S)&1) ans+=1/(1-p[(n-1)^S]);
        else ans-=1/(1-p[(n-1)^S]);
    }
    printf("%.10lf\n",ans);
    return 0;
}