BZOJ4036 [HAOI2015]按位或 【minmax容斥 + 期望 + FWT】题目链接题解

题目链接

BZOJ4036

题解

好套路的题啊，，，

我们要求的，实际上是一个集合(n)个(1)中最晚出现的(1)的期望时间
显然(minmax)容斥
[E(max{S}) = sumlimits_{T subseteq S} (-1)^{|T| + 1}E(min{T})]
那么问题就转化为了求每个集合中最早出现的(1)的期望时间
假如在(k)时刻出现，那么前(k - 1)时刻一定都是取的补集的子集，记(T)补集的所有子集概率和为(P)
[E(min{T}) = sumlimits_{k = 1}^{infty}kP(1 - P)^{k - 1}]
是一个离散变量的几何分布
设(P(x = a) = p)
那么取到(a)的期望为
[ begin{aligned} E(x = a) &= sumlimits_{k = 1}^{infty}k(1 - p)^{k - 1}p \ &= psumlimits_{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) &= pfrac{1}{p^2} \ &= frac{1}{p} end{aligned} ]

非常棒
于是有
[E(min{T}) = frac{1}{1 - P}]
我们只需要求出所有集合的子集概率和就好了
其实就是或运算的(FWT)

然后就切掉辣
复杂度(O(n2^n))
代码非常短

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
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("%.9lfn",ans);
    return 0;
}