[Luogu 3175] [HAOI2015]按位或

Posted on | Edited on | In , | Views:

题目链接

Luogu 3175 [HAOI 2015] 按位或

做法

为了表述的方便，下面称集合S为状态S，因为集合S本质上是表示二进制上某些位为1，某些位为0的状态，
定义S中的权值为S这个状态的每一位1出现的期望时间。
直接套Min-Max容斥的结论，

$E(Max(2^{n}-1))$就是我们要求的答案。
对于$E(Min(S))$，考虑定义，它的值应该等于所有与S有交集的状态的概率和，再取倒数。
即
有交集的状态不好求，那么考虑求与我没有交集的状态，显然这些状态就是我补集的子集，所以我们先FWT一下求出子集和，然后暴力套公式就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (25)
using namespace std;
int n,lim,d;
int pc[1<<20];
double p[1<<20],ans; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline void FWT(double *f){
    for (int i=1;i<lim;i<<=1){
        for (int j=0;j<lim;j+=(i<<1)){
            for (int k=j;k<i+j;k++){
                f[i+k]+=f[k];
            }
        }
    }
}
int main(){
    read(n);
    for (int i=0;i<(1<<n);i++) scanf("%lf",&p[i]);
    for (int i=0;i<(1<<n);i++) pc[i]=pc[i>>1]+(i&1);
    lim=1<<n;
    FWT(p);
    for (int i=1;i<(1<<n);i++){
        double k=1-p[(1<<n)-1-i];
        if (pc[i]&1) d=1;
        else d=-1;
        if (k==0){
            puts("INF");
            return 0;
        }
        ans=ans+(1/k)*d;
    }
    printf("%.10lf",ans);
    return 0;
}