[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}$。