[HAOI2015]按位或

按位或

考点：min - max 容斥 ， FWT， FMT

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

$$E(minS) = \frac{1}{\Sigma_{T \cap S \not= \phi}P_T}$$

$$= \frac{1}{1 - \Sigma_{T \cap S = \phi}P_T}$$

$$= \frac{1}{1 - \Sigma_{T \cap {(U-S)} = T}P_T}$$

$$= \frac{1}{1 - \Sigma_T\subseteq{(U - S)}P_T}$$

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

直接套用FWT即可

$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;
}