P3175 [HAOI2015] 按位或
题目大意
有一个长度为 n 且每一位都是 0 的数,接下来会在 [0,2n) 之间等概率给出整数 x 并与原数按位或,则这个数变为 2n−1 的抽取数的数量的期望值为多少?
数据范围:1≤n≤20。
前置知识
题解
首先考虑进行拆位,设 S 为这 n 个二进制位组成的集合,原数变成 2n−1 等价于所有位都变成 1,由于 max 不好求,考虑 Max-min 容斥,则有:
E(max(S))=T⊆ST=∅∑(−1)∣T∣−1E(min(T))
其中 E(min(T)) 表示 T 中若干位变为 1 的期望值。
设抽到一个与 T 有交集的数字概率为 P(T),则 E(min(T))=P(T)1,直接求交集很难,正难则反,P(T)=1−P(抽到的数与 T 交集为空集)。
也就是说,我们需要快速计算 S/T(S 中除去 T)的子集,令其概率为 Sum(S/T),考虑如何计算。
由于直接处理复杂度为 O(3n),考虑使用高维前缀和,在 O(n2n) 复杂度内预处理出 Sum 数组,最后带入容斥公式即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef double DB;
const int N = 20;
int n;
DB sum[1<<N];
int cnt[1<<N];
int main() {
scanf("%d" , &n);
for(int i = 0 ; i < (1<<n) ; i ++) {
scanf("%lf" , &sum[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 >> i) & 1)
sum[j] += sum[j^(1<<i)];
DB res = 0;
for(int i = 1 ; i < (1<<n) ; i ++) {
DB x = 1.0-sum[((1<<n)-1)^i];
if(x > 1e-8) {
if(cnt[i] & 1) res += 1/x;
else res -= 1/x;
}
}
if(res < 1e-10) puts("INF");
else printf("%.9lf\n" , res);
return 0;
}