题目概述

我写过了来着，鸽了。

解题报告

用Min-Max容斥再做一遍这题，学习自memset0。

Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S)$ 和子集 $T$ 的最小值 $min(T)$ 的关系如下：

$$ max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T) $$

证明：设 $S$ 中 $a_{x+1}$ 为第 $x+1$ 大的数（有 $x$ 个数比 $a_{x+1}$ 大），则所有 $min(T)=a_{x+1}$ 的集合 $T$ 的总贡献为

$$ a_{x+1}\sum_{i=0}^{x}(-1)^{(i+1)-1}{x\choose i}=a_{x+1}\sum_{i=0}^{x}(-1)^i{x\choose i}=a_{x+1}(1-1)^{x} $$

那么对于所有 $x$ ，总贡献就是：$\sum_{x=0}^{|S|-1}a_{x+1}\cdot0^{x}$ ，只有在 $x=0$ 也就是选了最大值时有贡献，所以原式得证。

2019.1.31UPD：重新填一下构造的坑。

构造容斥系数 $f(i)$ 使得 $max(S)=\sum_{T\subseteq S}f(|T|)min(T)$ ，那么同证明可以得出总贡献：

$$ \sum_{x=0}^{|S|-1}a_{x+1}\sum_{i=0}^{x}f(i+1){x\choose i} $$

因为 $max(S)=a_1$ ，所以 $\sum_{i=0}^{x}f(i+1){x\choose i}=[x=0]​$ ，根据二项式反演：

$$ f(x+1)=\sum_{i=0}^{x}(-1)^{x-i}{x\choose i}[i=0]=(-1)^x $$

所以 $f(i)=(-1)^{i-1}$ 即 $max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)$ 。

这道题对于一个集合 $S$ ，可以令 $max(S)$ 表示 $S$ 集合中最晚出现的元素第一次出现的期望时间，那么对应的 $min(S)$ 就表示 $S$ 集合中最早出现的元素第一次出现的期望时间，可以得到：

$$ max(S)=\sum_{T\subseteq S}(-1)^{|T|-1}min(T)\\ min(T)={1\over\sum_{A\cap T\not=\emptyset}P_A}={1\over 1-\sum_{A\cap T=\emptyset}P_A}={1\over1-\sum_{(U-A)\cap T=T}P_A} $$

所以就可以用高维前缀和求出 $min(T)$ ，然后求出答案 $max(U)$。

ps：发生概率为 $p$ 的事件一直重复，则发生的期望时间为 $1\over p$ ，证明的话考虑错位相减和等比数列求和：

$$ S(k)=p\sum_{i=1}^{k}i(1-p)^{i-1}\\ S(k)-(1-p)S(k)=pS(k)=(p\sum_{i=1}^{k}(1-p)^{i-1})-pk(1-p)^k=1-(pk+1)(1-p)^{k}\\ k\to+\infty,pS(k)=1,S(k)={1\over p} $$

示例程序

#include<cstdio>
using namespace std;
typedef long double DB;
const int maxn=20,maxs=1<<maxn;

int n,S,cnt[maxs];DB f[maxs],ans;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);S=1<<n;for (int i=0;i<S;i++) {double x;scanf("%lf",&x);f[(~i)&(S-1)]=x;}
    for (int i=0;i<n;i++) for (int j=1<<i;j<S;j=(j+1)|(1<<i)) f[j^(1<<i)]+=f[j];
    for (int i=1;i<S;i++){
        cnt[i]=cnt[i>>1]+(i&1);if (f[i]==1) return puts("INF"),0;
        f[i]=1/(1-f[i]);cnt[i]&1?ans+=f[i]:ans-=f[i];
    }return printf("%.10f\n",(double)ans),0;
}