[HAOI2015] 按位或

传送门
BZOJ怎么挂掉了。。

因为这题有点东西，所以单开一篇。。

min-max容斥：
\[min(S)=\sum_{T \subseteq S} (-1)^{|T|-1}min(T)\]

这东西在期望意义下也成立 -_-!

回到这题，全部变成 1 的时间就是每个位变成 1 的时间取max，但这东西还是不好求。
但是一个集合最早有 1 的时间还是可求的。。

对于一个集合 \(T\)，设它的状态是 \(mask\) ，一次操作与它有交的概率就是 \[\sum_{i \& mask \ne 0} p[i]\]

设 \(C=(1<<n) \oplus mask\)，即 \(mask\) 的补集，上面的柿子就等于 \[1-\sum_{i \& C=i} p[i]\]

这个东西呢，似乎可以FWT也可以FMT，然而我都不会QAQ

前几天get到一个叫SOS-DP的东西，也可以做。然后一交发现MLE了！！囧TZ
改成滚动数组就过了QAQ

网上有人说FWT和SOS-DP是一样的，总之我现在对FWT & FMT & SOS-DP这三种东西是懵逼的……

#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=21;
int n;
double p[1<<N],dp[2][1<<N];

void read(int &x){
    char ch=getchar();x=0;
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}

int main(){
    read(n);
    int all=0;
    frl(i,0,1<<n){
        scanf("%lf",&p[i]);
        if (p[i]!=0) all|=i;
    }
    if (all!=(1<<n)-1) return puts("INF"),0;
    int cur=0;frl(i,0,1<<n) dp[0][i]=p[i];
    fr(j,1,n){
        cur^=1;
        frl(i,0,1<<n)
         if (i&(1<<j-1)) dp[cur][i]=dp[cur^1][i]+dp[cur^1][i^(1<<j-1)];
          else dp[cur][i]=dp[cur^1][i];
        //printf("%.6lf ",dp[i][n]);
    }
    //cout<<endl;
    double ans=0;
    frl(i,1,1<<n){
        int T=0;
        frl(j,0,n) if (i&(1<<j)) T++;
        if (T&1) ans+=1.0/(1-dp[cur][all^i]);
         else ans-=1.0/(1-dp[cur][all^i]);
    }
    printf("%.8lf\n",ans);
    return 0;
}

[HAOI2015] 按位或

原文：https://www.cnblogs.com/ymzqwq/p/11619608.html