Luogu3175 按位或 | Arahc's Home

题面

简化题意

有一个变量 $a$ ，初始为 $0$ 。每次在 $[0,2^n-1]$ 中随机选择一个数并让 $a$ 或上它。给定每个数选择的概率，求期望多少次能使 $a=2^n-1$ 。

题解

离散随机变量：一个取值范围为一些特定的不连续值的随机变量，比如随机取一个自然数。

如果离散随机变量 $x$ 满足如下式子（ $n$ 为常数），则称这个离散随机变量服从参数 $n$ 的几何分布：

P(x=k) = n(1-n)^{k-1} \qquad k\in \mathbb{N}^+

这个东西满足一个结论：

E(x) = \frac{1}{n}

感性理解就是，假设 xf 有 $\frac{1}{100000}$ 的概率不和 aa 贴贴， $\frac{99999}{100000}$ 的概率贴贴。那么 aa 恰好在第 $k$ 天发现以前每天都贴贴，但今天 xf 没有和他贴贴的概率为：

\left( \frac{99999}{100000} \right)^{k-1} \times \frac{1}{100000}

不难发现贴贴事件符从参数 $\frac{1}{100000}$ 的几何分布，因此 xf 期望 $100000$ 天即大约 $274$ 年里会有一天不贴贴。可以看出期望就是 $\frac{1}{n}$ 。

理性理解就是：

\begin{aligned} E(x) &= \sum_i i P(x=i) \\ &= n\sum_i i(1-n)^{i-1} \\ &= n\left[ \sum_i i(1-n)^i + \sum_{i=0}(1-n)^i \right] \\ &= n(\frac{1-n}{n^2} + \frac{1}{n}) \\ &= \frac{1}{n} \end{aligned}

回到这个问题，考虑用 minmax 容斥，转化为对于所有集合 $T\subseteq S$ ， $T$ 中至少有一个变成 $1$ 的最早时间。记 $P(\min T = k)$ 表示前 $k-1$ 次没有选中，第 $k$ 次恰好选中的概率：

P(\min T = k) = ( 1-P(S\cap T \neq \varnothing) )^{k-1} P(S\cap T \neq \varnothing)

到这里，只要能求出 $P(S\cap T \neq \varnothing)$ 就结束了。

将集合写成变量的二进制位，也就是转化为 $P(S\oplus T)$ 。所以问题直接转化为怎么求 $P(T)$ 。考虑 FWT 的按位或卷积。对原概率数组求一遍 FWT，就能求出所有 $P(T)$ 了。

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=2000006;

int n,S,sz[max_n];
long double ans,f[max_n];

inline void OR(){ // FWT
	for(register int k=1,l=2;l<=S;l<<=1,k<<=1)
		for(register int i=0;i<S;i+=l)
			for(register int j=0;j<k;++j)
				f[i+j+k]+=f[i+j];
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;S=(1<<n);
	for(register int i=0;i<S;++i)
	    cin>>f[i];
	OR();
	for(register int i=1;i<S;++i)
	    sz[i]=sz[i>>1]+(i&1);
	for(register int i=1;i<S;++i){
	    if(1-f[(S-1)^i]<0.000000001){
	        puts("INF");
	        return 0;
	    }
	    ans+=(sz[i]&1?1:-1)*((long double)1/(1-f[(S-1)^i]));
	}
	printf("%.15Lf",ans);
	return 0;
}