自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:47:50，当前版本为作者最后更新于2023-07-10 13:28:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

C. P9379 [THUPC 2023 决赛] 老虎机

显然，我们只关心已经确定的位置集合 $A$。称 $A$ 合法，当且仅当 $A$ 可以确定目标串。

对于操作次数的期望，经典套路是根据期望的线性性，求出到达每个不合法状态的概率 $P_S$，乘以停留在该状态的期望时间 $t_S$，再求和。注意到 $A$ 合法则 $A$ 的超集合法，因此最终求答案时需要的 $P$ 和 $t$ 和目标串无关，即若一个状态不合法，则到达它的概率不受到目标串的影响，考虑预处理。

设 $p_S$ 表示停留在状态 $S$ 的概率，则 $p_S = \prod_{i\notin S} (1 - p_i)$。根据经典结论，$t_S = \sum_{x = 0} ^ {+\infty} p_S ^ x = \frac {1} {1 - p_S}$，即 $x$ 次操作后仍停留在 $S$ 的概率乘以代价 $1$，求和。

从 $P_S\to P_T$ 的转移系数为 $\frac {\prod_{i\notin T} (1 - p_i) \prod_{i\in T\land i\notin S} p_i} {1 - p_S}$。预处理 $f_S = \prod_{i\in S} p_i$，$g_S = f_S \prod_{i\notin S} (1 - p_i)$，则系数为 $\frac {g_T} {f_S - g_S}$。枚举超集 DP，时间复杂度 $\mathcal{O}(3 ^ l)$。这部分也可以做到 $\mathcal{O}(2 ^ ll)$（类似 A 题按位处理）。

对于目标串 $s_i$，设 $T_i$ 表示多少个已知位置集合使得可以唯一确定 $s_i$，即 $s_i$ 的合法位置集合，则答案为 $\sum_{A\notin T} P_At_A$。

显然，对于任意 $A$，它不会出现在超过 $2 ^ {|A|}$ 个 $T_i$ 中。因此 $\sum |T_i| \leq 3 ^ l$。考虑补集转化，将答案写成 $\sum_{A} P_At_A - \sum_{A\in T_i} P_At_A$。前者在预处理 $P, t$ 时直接求，关键在于如何求 $T_i$。

其实也不难。设 $h_{S, T}$ 表示位置集合为 $S$ 时，状态为 $T$ 的唯一的串的标号。如果没有则为 $0$，如果有多个则为 $-1$。初始化 $h_{U, s_i} = i$，其中 $U$ 是全集 $\{0, 1, \cdots, l - 1\}$。$h_S$ 容易从 $h_{S\cup \{x\}}$ 转移过来，其中 $x$ 是任意一个不属于 $S$ 的位置。如果 $h_{S, T} = i$，则将 $s_i$ 的答案减去 $P_S t_S$。

时间复杂度 $\mathcal{O}(3 ^ l)$。代码。