按位或[HAOI2015]

AK-dream

发布于：2021年1月4日

次浏览

题目描述

刚开始你有一个数字$0$，每一秒钟你会随机选择一个$[0,2^n-1]$的数字，与你手上的数字进行或（C++, C 的 |， Pascal 的 or）操作。选择数字$i$ 的概率是$p[i]$（保证$0\le p[i]\le 1,\ \sum p[i]=1$） 问期望多少秒后，你手上的数字变成$2^n-1$。

题解

min-max容斥：

.$\max(S)$表示集合$S$的最大元素

证明大概就是除了$\max(S)$剩一个，其他都加加减减消掉了。。。

如果我们设$E(x)$表示二进制中$x$这一位第一次变成$1$的期望步数，则有

.$\max\limits_{x\in S}E(x)=\sum\limits_{T \subset S \cap T \neq \varnothing} (-1)^{|T|+1}\min\limits_{y\in T}E(y)$

.$\max\limits_{x\in S}E(x)$也就是$S$中所有位都变成$1$的期望步数，$\min\limits_{x\in S}E(x)$即为$S$中至少有$1$位变成$1$的期望步数

考虑后者怎么求，一步就使得$S$中至少有$1$位变成$1$的概率为$(1-\sum\limits_{i\cap S=\varnothing} p[i])$，所以期望步数就是$\dfrac{1}{1-\sum\limits_{i\cap S=\varnothing} p[i]}$

假设$S_0$为$S$的补集，那么$\sum\limits_{i\cap S=\varnothing} p[i]=\sum\limits_{i\subseteq S_0} p[i]$，右式可以用FMT或者状压DP在$O(n2^n)$的复杂度中求得 那么$\min\limits_{x\in S}E(x)=\dfrac{1}{1-\sum\limits_{i\subseteq S_0} p[i]}$然后套用上面的minmax容斥即可 答案即为$\max\limits_{x\in S}E(2^n-1)$

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

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

更新于：2021年1月4日

FWT