题目概述

初始时你有一个数字 $0$，每秒随机选择 $[0, 2^n-1]$ 中的一个数，与当前数字进行按位或操作。选择数字 $i$ 的概率为 $p[i]$。求期望多少秒后数字变成 $2^n-1$。

问题分析

这是一个典型的集合覆盖期望时间问题，可以通过以下方法解决：

关键思路

1. 状态表示：将每个状态看作一个二进制集合，目标是从空集 $\emptyset$ 到达全集 $U = 2^n-1$。

2. Min-Max容斥：将到达全集的期望时间转化为每个子集第一次被覆盖的时间的容斥计算。

3. 集合幂级数：使用快速莫比乌斯变换（FMT）在 $O(n2^n)$ 时间内处理高维前缀和。

核心算法

1. Min-Max容斥应用

设 $T_i$ 表示第 $i$ 个元素第一次被覆盖的时间，则：

$$E[\max_{i \in U} T_i] = \sum_{S \subseteq U} (-1)^{|S|+1} E[\min_{i \in S} T_i] $$

2. 期望计算

对于子集 $S$，每一步覆盖 $S$ 中至少一个元素的概率为：

$$P_S = \sum_{T \cap S \neq \emptyset} p_T$$

则首次覆盖时间的期望为：

$$E[\min_{i \in S} T_i] = \frac{1}{P_S}$$

3. 概率计算优化

通过补集转换：

$$P_S = 1 - \sum_{T \cap S = \emptyset} p_T = 1 - \sum_{T \subseteq \overline{S}} p_T $$

使用FMT计算每个集合的子集和即可在 $O(n2^n)$ 时间内完成。

算法步骤

1. 输入处理：读入 $n$ 和概率数组 $p$
2. FMT预处理：计算每个集合的子集概率和
3. 容斥计算：枚举所有非空子集，根据容斥原理计算期望
4. 特判处理：如果全集不可达则输出 INF

复杂度分析

• 时间复杂度：$O(n2^n)$
• 空间复杂度：$O(2^n)$

技术要点

• 快速莫比乌斯变换：用于高效计算高维前缀和
• 容斥原理：处理最值期望的经典方法
• 概率收敛性：需要检查概率分布是否保证最终能覆盖全集

总结

本题是Min-Max容斥在期望问题中的典型应用，结合快速集合变换技术，在状态空间指数级的情况下仍能高效求解。