[HAOI2015]按位或

题目

好神的题啊

我们发现我们求这个东西如果常规\(dp\)的话可以建出一张拓扑图来，但是边的级别高达\(3^n\)，转移的时候还要解方程显然不能通过本题

我们考虑神仙的\(min-max\)容斥

设\(Emax(S)\)表示集合\(S\)中最晚出现的那个自己出现的期望时间，\(Emin(S)\)表示集合\(S\)最早出现的那个子集出现的期望时间

我们套上公式

\[Emax(S)=\sum_{T\subseteq S}(-1)^{|T|+1}Emin(T)\]

我们考虑\(Emin(T)\)怎么求，显然只需要一个跟\(T\)有交的子集就可以了

于是

\[Emin(T)=\frac{1}{\sum_{j\cap T\ne \varnothing }p_j}\]

发现有交好像不是很好求，我们正难则反一下

求\(1-\sum_{j\cap T= \varnothing }p_j\)，考虑到和\(T\)没有交的集合必然是\(T\)的补集的子集，于是我们求一个子集和就好了

回忆\(fwt\)的\(or\)卷积的第一步，我们求出来是\(\sum_{j|i=i}p_j\)，就是子集和

于是我们套一个\(fwt\)即可

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define eps 1e-10
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=(1<<20)+12;
int n,len,cnt[maxn];
double p[maxn];
inline void Fwtor(double *f) {
    for(re int i=2;i<=len;i<<=1)
        for(re int ln=i>>1,l=0;l<len;l+=i)  
            for(re int x=l;x<l+ln;++x)
                f[x+ln]+=f[x];
}
inline int check(double a) {return a+eps>0&&a-eps<0;}
int main() {
    scanf("%d",&n);len=(1<<n);
    for(re int i=0;i<len;i++) scanf("%lf",&p[i]);
    Fwtor(p);double ans=0;
    for(re int i=1;i<len;i++) {
        cnt[i]=cnt[i>>1]+(i&1);
        if(check(1.0-p[(len-1)^i])) {
            puts("INF");return 0;
        }
        if(cnt[i]&1) ans+=1.0/(1.0-p[(len-1)^i]);
            else ans-=1.0/(1.0-p[(len-1)^i]);
    }
    printf("%.10lf\n",ans);
    return 0;
}

[HAOI2015]按位或

原文：https://www.cnblogs.com/asuldb/p/10685498.html