按位或

考点:min - max 容斥 , FWT, FMT

这一题一看就知道是Min-Max容斥,下面讲一下如何求
E(minS)E(minS)

E(minS)=1ΣTSϕPTE(minS) = \frac{1}{\Sigma_{T \cap S \not= \phi}P_T}

=11ΣTS=ϕPT= \frac{1}{1 - \Sigma_{T \cap S = \phi}P_T}

=11ΣT(US)=TPT= \frac{1}{1 - \Sigma_{T \cap {(U-S)} = T}P_T}

=11ΣT(US)PT= \frac{1}{1 - \Sigma_T\subseteq{(U - S)}P_T}

这时直接枚举即可O(4n)O(4^n)

直接套用FWT即可

O(n2n)O(n2^n)

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1050000;
double eps = 1e-10;

int n , up , Size[N];
double Num[N] , res;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    up = (1 << n);
    for(int i = 0;i < up;i++)
        cin >> Num[i];
    for(int k = 1;k < up;k <<= 1) {
        for(int s = 0;s < up;s += k << 1) {
            for(int i = s;i < s + k;i++) {
                double a0 = Num[i];
                double a1 = Num[i + k];
                Num[i] = a0;
                Num[i + k] = a0 + a1;
            }
        }
    }
    for(int i = 1;i < up;i++)
        Size[i] += Size[i >> 1] + (i & 1);
    for(int i = 1;i < up;i++) {
        if(1 - Num[(up - 1) ^ i] < eps) {
            puts("INF");
            return 0;
        }
        double ex = 1 / (1 - Num[(up - 1) ^ i]);
        if(Size[i] % 2) {
            res += ex;
        }
        else {
            res -= ex;
        }
    }
    ios::sync_with_stdio(true);
    printf("%.10lf" ,res);
    return 0;
}