P3175 [HAOI2015] 按位或

你手上有一个数，初始为 $0$，每秒随机选择一个 $[0,2^n)$ 的数与你手上的数或，选择 $i$ 的概率为 $p_i$，求你手上的数变为 $2^n - 1$ 的期望时间。

$1 \le n \le 20$。

法一

min-max 容斥，直接背式子

$$\mathrm{kthmax}(S) = \sum_{T \subseteq S} (-1)^{|T|-1} \binom{|T|-1}{k-1} \min(T)$$

期望意义下也是成立的，证明比较扭曲。

记 $f_{i}$ 为第 $i$ 位变为 $1$ 的时间，套 min-max 容斥即可。

法二

定义乘法为或卷积，那么 $k$ 秒后手上的数为 $S$ 的概率为 $p^{k}_{S}$。记 $f_{S}$ 为数为 $S$ 的期望时间，那么

$$f_{S} = \sum_{k=1}^{\infty} k(p^{k}_{S} - p^{k-1}_{S})$$

记 $f,p$ 莫比乌斯变换的结果为 $F,P$，那么

$$\begin{aligned} F_{S} &= \sum_{k=1}^{\infty} k(P^{k}_{S} - P^{k-1}_{S}) \\ &= -\sum_{k=0}^{\infty} P_{S}^{k} \\ &= \left\{\begin{matrix} -\frac{1}{1-P_{S}} & (P_S \neq 1) \\ 0 & (P_S=1) \end{matrix}\right. \end{aligned}$$