【题解】[HAOI2015] 按位或

[HAOI2015]按位或

开始手上有数字 $0$ ，每秒按照一定概率选择一个 $[0,2^n-1]$ 之内的数字，将手上的数字或上他。问手上的数变成 $2^n-1$ 的期望秒数。
$n\le 20$，满足 $\sum p_i = 1$

$\texttt{Solution}$

首先考虑 $\texttt{Min-Max}$ 容斥，有这个柿子：

$$\max(S) = \sum_{\varnothing \ne S \subseteq T} (-1)^{|T|-1} \min(T)$$

套上期望也是成立的。

那么设 $\max(S),\min(S)$ 分别为 $S$ 这个数字中最后/最先或上的数字的期望时间。然后就可以套用以上的柿子，用 $\min(S)$ 求 $\max(S)$。

考虑 $\min(S)$ ，发现：

$$\min(S) = \dfrac{1}{\sum_{S \cap T \ne \varnothing} p_T}$$

下面的东西：

$$\sum_{S \cap T \ne \varnothing} p_T= 1 - \sum_{S \cap T = \varnothing} p_T$$

令 $S'$ 为 $S$ 的补集，那么上式变为：

$$1 - \sum_{T \subseteq S'} p_T$$

后面的部分实际就是 $S'$ 的子集和，可以直接一遍 $\texttt{FWT}$。