题目链接

题解

好套路的题啊，，，

我们要求的，实际上是一个集合\(n\)个\(1\)中最晚出现的\(1\)的期望时间

显然\(minmax\)容斥

\[E(max\{S\}) = \sum\limits_{T \subseteq S} (-1)^{|T| + 1}E(min\{T\})\]

那么问题就转化为了求每个集合中最早出现的\(1\)的期望时间

假如在\(k\)时刻出现，那么前\(k - 1\)时刻一定都是取的补集的子集，记\(T\)补集的所有子集概率和为\(P\)

\[E(min\{T\}) = \sum\limits_{k = 1}^{\infty}kP(1 - P)^{k - 1}\]

是一个离散变量的几何分布

设\(P(x = a) = p\)

那么取到\(a\)的期望为

\[ \begin{aligned} E(x = a) &= \sum\limits_{k = 1}^{\infty}k(1 - p)^{k - 1}p \\ &= p\sum\limits_{k = 1}^{\infty}k(1 - p)^{k - 1} \end{aligned} \]

记\(f(x) = 1 + 2x + 3x^2 + 4x^3 + \dots\)

则\(xf(x) = x + 2x^2 + 3x^3 + 4x^4 + \dots\)

则\((1 - x)f(x) = 1 + x + x^2 + x^3 + \dots\)

对于\(0 < x < 1\)，\((1 - x)f(x)\)是收敛的，可以取到

\[(1 - x)f(x) = \frac{1}{1 - x}\]

\[f(x) = \frac{1}{(1 - x)^2}\]

所以

\[ \begin{aligned} E(x = a) &= p\frac{1}{p^2} \\ &= \frac{1}{p} \end{aligned} \]

非常棒

于是有

\[E(min\{T\}) = \frac{1}{1 - P}\]

我们只需要求出所有集合的子集概率和就好了

其实就是或运算的\(FWT\)

然后就切掉辣

复杂度\(O(n2^n)\)

代码非常短

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int maxn = (1 << 20);int n,N,cnt[maxn];double p[maxn],ans;int main(){    scanf("%d",&n); N = (1 << n);    for (int i = 0; i < N; i++) scanf("%lf",&p[i]);    for (int i = 1; i < N; i <<= 1)        for (int j = 0; j < N; j += (i << 1))            for (int k = 0; k < i; k++)                p[j + k + i] += p[j + k];    for (int i = 1; i < N; i++) cnt[i] = cnt[i >> 1] + (i & 1);    for (int i = 1; i < N; i++){        if (1.0 - p[(N - 1) ^ i] < 1e-9){puts("INF"); return 0;}        ans += ((cnt[i] & 1) ? 1.0 : -1.0) * (1.0 / (1 - p[(N - 1) ^ i]));    }    printf("%.9lf\n",ans);    return 0;}