「HAOI2015」按位或

这一道题还是挺好玩的啦。

传送门

洛谷P3175

BZOJ4036

题解

考虑Min-Max容斥。

设$T(i)$表示二进制数的第$i$位变成$1$的时间,那么题目里要求的就是:

但是要注意,一般情况下并没有

并且这道题中最大值并不好求,所以这里就要用Min-Max容斥,令$S=\lbrace T(i)|i\in[1,n]\rbrace$,于是就有:

考虑后面那个式子怎么求。

令$P(T)$表示选中的位的集合是$T$的子集的概率,可以用高位前缀和预处理出来。

考虑如何计算$min(T)=K$的概率。

当$min(T)=K$时,前$K-1$次选择的位的集合都是$T$的补集的子集,第$K$次则不是$T$的补集的子集。

所以概率就为$P(U\bigoplus T)^{K-1}\cdot(1-P(U\bigoplus T))$。

于是

然后暴力枚举$T$累加贡献即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
using namespace std;
const int maxn=(1<<20)+5;
int n,cnt[maxn];double S[maxn],ans;
int main()
{
scanf("%d",&n);
for(int i=0;i<(1<<n);i++){scanf("%lf",&S[i]);cnt[i]=cnt[i>>1]+(i&1);}
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
if(j&(1<<i))
S[j]+=S[j-(1<<i)];
for(int i=0;i<(1<<n)-1;i++)
{
ans+=((n-cnt[i])&1?1:-1)/(1-S[i]);
if(S[i]==1){printf("INF\n");return 0;}
}
printf("%lf\n",ans);
return 0;
}