LOJ #2127. 「HAOI2015」按位或 （min-max 容斥 + FWT）

#include <bits/stdc++.h>    
#define N 21   
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;       
int bin[N],size[1<<N],n;
double p[1<<N],F[1<<N],g[1<<N],A[1<<N],B[1<<N];              
void exi() { printf("INF\n"),exit(0); }
int lowbit(int x) { return x&(-x); }      
void FWT(double *a,int len) 
{
    for(int i=1;i<len;i<<=1) 
        for(int j=0;j<len;j+=i<<1)   
            for(int k=0;k<i;++k) 
                a[j+k+i]+=a[j+k];    
}                    
int main() 
{ 
    // setIO("input");    
    bin[0]=1;   
    for(int i=1;i<N;++i) bin[i]=bin[i-1]<<1;    
    scanf("%d",&n); 
    int is=0,to=bin[n]-1;    
    for(int i=0;i<bin[n];++i) 
    {  
        scanf("%lf",&p[i]),F[i]=p[i];     
        if(p[i]) is|=i;    
    }   
    if(is!=bin[n]-1) 
        exi();            
    for(int i=1;i<bin[n];++i)
        size[i]=size[i-lowbit(i)]+1;          
    FWT(F,bin[n]);    
    double ans=0;     
    for(int i=1;i<bin[n];++i) 
    {            
        double opt=(size[i]%2)?1:-1;              
        ans+=opt/(1.0-F[to^i]);       
    }       
    printf("%.8f\n",ans);    
    return 0;   
}