[HAOI2015]按位或——Min-Max容斥+FWT

题面

　　Bzoj4036

解析

　　考虑$ans=E(max(t[i])), iin S, S=egin{Bmatrix} 1,2,cdots, nend{Bmatrix}$，这里$t[i]$表示第$i$位变成$1$的时间，$E(max(t[i]))$表示最后变成$1$的一位的期望时间，暂时记为$E(max(S))$，注意这个不等于$max(E(S))$

　　然后套上$Min-Max$容斥，$ans=sum_{T subseteq S}(-1)^{|T|+1}*E(min(T))$，$E(min(T))$表示$T$中至少有一位变成$1$的期望时间。

　　$E(min(T))$似乎不太好求，考虑补集转换，$E(min(T))=frac{1}{1-sum_{icap T=varnothing }p[i]}$，$p$为题目中给出的数组，若将$T$视为二进制数，则$E(min(T))=frac{1}{1-sum_{i&T=0}p[i]}$

　　而$sum_{i&T==0}p[i]$就等于$T$的补集的子集和，因此只需要$FWT(or)$一次就可以了。

　代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = (1 << 20) + 5;
const double eps = 1e-11;

int n, m, num[maxn];
double a[maxn];
bool used[25];

void FWT_or(double *x)
{
    for(int i = 1; i <= m; i <<= 1)
        for(int j = 0; j <= m; j += (i << 1))
            for(int k = 0; k < i; ++k)
                x[i+j+k] += x[j+k];
}

int main()
{
    scanf("%d", &n);
    m = (1 << n) - 1;
    for(int i = 0; i <= m; ++i)
    {
        scanf("%lf", &a[i]);
        num[i] = num[i>>1] + (i & 1);
        if(a[i] > eps)
        {
            for(int j = 0; j < n; ++j)
                if((i >> j) & 1)
                    used[j] = 1;
        }
    }
    for(int j = 0; j < n; ++j)
        if(!used[j])
        {
            printf("INF");
            return 0;
        }
    FWT_or(a);
    double ans = 0;
    for(int i = 1; i <= m; ++i)
        ans += ((num[i] & 1)? 1: -1) / (1 - a[m^i]);
    printf("%.10f", ans);
    return 0;
}