P9379 [THUPC 2023 决赛] 老虎机

· · 题解

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)。代码。