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