题目描述
刚开始你有一个数字,每一秒钟你会随机选择一个的数字,与你手上的数字进行或(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; }
|