题目描述

刚开始你有一个数字,每一秒钟你会随机选择一个的数字,与你手上的数字进行或(C++, C 的 |, Pascal 的 or)操作。选择数字 的概率是(保证) 问期望多少秒后,你手上的数字变成

题解

min-max容斥:

.表示集合的最大元素

证明大概就是除了剩一个,其他都加加减减消掉了。。。

如果我们设表示二进制中这一位第一次变成的期望步数,则有

.

.也就是中所有位都变成的期望步数,即为中至少有位变成的期望步数

考虑后者怎么求,一步就使得中至少有位变成的概率为,所以期望步数就是

假设的补集,那么,右式可以用FMT或者状压DP在的复杂度中求得 那么然后套用上面的minmax容斥即可 答案即为

无解判断方法很多也很好判断就不说了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define N 1100005
using namespace std;
typedef long long ll;

int n;
double a[N], ans;

void FWT(double *F) {
for (int i = 1; i < (1<<n); i<<=1) {
for (int p = i<<1, j = 0; j < (1<<n); j += p) {
for (int k = 0; k < i; k++) {
double x = F[j+k], y = F[j+k+i];
F[j+k] = x; F[j+k+i] = x + y;
}
}
}
}

int main() {
scanf("%d", &n);
for (int i = 0; i < (1<<n); i++) scanf("%lf", &a[i]);
FWT(a);
for (int i = 1; i < (1<<n); i++) {
if (1.0-a[((1<<n)-1)^i] <= 1e-8) {
puts("INF"); return 0;
}
if (__builtin_popcount(i) & 1) ans += 1.0 / (1.0-a[((1<<n)-1)^i]);
else ans -= 1.0 / (1.0-a[((1<<n)-1)^i]);
}
printf("%.10lf", ans);
return 0;
}

评论