Luogu3175 [HAOI2015]按位或


Description

刚开始你有一个数字 \(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\)

$n $

Solution

注意到每个位是独立的,设随机变量 \(a_i\) 为第 \(i\) 位第一次变成 \(1\) 的时间,即求 \(E(\max(a_i))\)。 我们有 \(\min-\max\) 容斥:

\[ E(\max(S))=\sum_{T\subseteq S}(-1)^{|T|-1}E(\min(T)) \]

感性理解即,我们求出了每个变量独自的贡献,然后减去两个变量相互影响时小的那个的贡献,再加上三个的贡献...

那么 \(E(\min(T))\) 的含义即这个随机变量集合中至少有一个 \(1\) 的期望时间。

那么只要求出一次实验能让集合中至少有一位变为 \(1\) 的 概率 \(P\) ,期望就是 \(1/P\)

也就是求 \[ \frac{1}{\sum_{G \cap T \neq \empty}P(G)} \] 好像不是很能求,转换一下可以变成求 \[ \frac{1}{1-\sum_{G\subseteq(U-T)}P(G)} \] 减号后面是个求子集和,那么 \(\operatorname{FWT}\) 一下就行啦。


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录