[HAOI2015]按位或

樸素的

f[S]表示S到(1<<n)的期望次數

發現1的個數只增加不減少

所以可以類似拓撲序的圖，然后枚舉子集O(3^n)轉移

沒有優化的余地

?

另辟蹊徑：

拆開每一位來看

t[i]表示第i位變成1的次數

ans=E(max(t[i]))

根據min-max容斥

得到：ans=∑E(t[i])-∑E(min(t[i],t[j]))+∑E(min(t[i],t[j],t[k])).....

考慮min(S)的含義：

使得這個S中的任意一位0變成1的期望次數！

操作一次變成1的概率tmp：(1-p(操作一次不包含S))

（這個用FMT）

（當然，可以直接計算操作一次包含S的概率，但是直接FMT會把0算上，，這個要特殊處理）

1/tmp就是期望次數

根據S的size的奇偶確定符號

?

代碼：

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=22;
double p[1<<20];
int sz[1<<20];
double ans;
int n;
int main(){rd(n);for(reg i=0;i<(1<<n);++i){scanf("%lf",&p[i]);sz[i]=sz[i>>1]+(i&1);}for(reg i=0;i<n;++i){for(reg j=0;j<(1<<n);++j){//    cout<<" i j "<<i<<" "<<j<<endl;if(j&(1<<i)) p[j]+=p[j^(1<<i)];}}
//    cout<<" FMT "<<endl;int s=(1<<n)-1;for(reg i=1;i<(1<<n);++i){int bu=s-i;double tmp;//    cout<<" bu "<<bu<<" p[bu] "<<p[bu]<<endl;if(p[bu]!=1.000) tmp=1/(1.0-p[bu]);else {puts("INF");return 0;}if(sz[i]&1){ans+=tmp;}else ans-=tmp;}printf("%.10lf",ans);return 0;
}}
signed main(){Miracle::main();return 0;
}/*Author: *Miracle*Date: 2019/1/4 22:15:10
*/

如果想到min-max容斥和式子

應該就比較好做了。

?

正難則反的原因是：

max要考慮最后一個變成1的次數，都要考慮上，太麻煩

min只要考慮第一個變成1的次數，有一個操作涉及S，就合法了。

?