题解：老虎机期望游戏币数

题目分析

我们有一个集合 $S$ 包含 $n$ 个长度为 $l$ 的 $\texttt{01}$ 串，老虎机随机选择一个 $s \in S$ 作为答案串。

每次拉杆（花费 1 游戏币）会得到一个信息串 $t$：

• 对于位置 $i$，有 $p_i$ 概率 $t_i = s_i$（获得真实信息）
• 有 $1-p_i$ 概率 $t_i = \texttt{?}$（无信息）

所有位置独立。

玩家在能唯一确定答案串时停止。对于每个可能的答案串 $t \in S$，求在最优策略下的期望游戏币数。

---

关键观察

1. 状态表示：
   在获得若干次观测后，玩家会有一个"候选集" $C \subseteq S$，包含所有与目前观测一致的字符串。
   当 $|C| = 1$ 时停止。

2. 状态转移：
   设当前候选集为 $C$，拉一次杆得到观测 $o$（一个长度为 $l$ 的串，每个位置是 $0/1/?$），
   然后候选集会更新为 $C' = \{s \in C \mid \forall i, o_i =\ ?\ \vee\ o_i = s_i\}$。

3. 概率计算：
   对于固定答案串 $s$，得到观测 $o$ 的概率是：

   $$\Pr(o \mid s) = \prod_{i=0}^{l-1} \begin{cases} p_i & \text{if } o_i = s_i \\ 1-p_i & \text{if } o_i =\ ? \\ 0 & \text{otherwise} \end{cases} $$

4. 最优策略：
   在状态 $C$ 下，最优策略是选择能最小化期望额外成本的拉杆次数。
   这可以用动态规划求解。

---

动态规划设计

设 $E[C]$ 表示当前候选集为 $C$ 时，在最优策略下还需要花费的期望游戏币数（假设答案在 $C$ 中）。

边界：如果 $|C| = 1$，则 $E[C] = 0$（已确定答案）。

转移：拉一次杆后，根据观测 $o$ 会转移到 $C_o = \{x \in C \mid x \text{ 与 } o \text{ 一致}\}$。

对于固定答案 $s \in C$，得到观测 $o$ 的概率为 $\Pr(o \mid s)$，且转移到的状态是 $C_o$。

因此：

$$E[C] = 1 + \min_{\text{策略}} \mathbb{E}[\text{未来成本}] $$

但"策略"在这里其实是固定的：我们只能拉杆观测，没有其他选择。所以：

$$E[C] = 1 + \sum_{s \in C} \frac{1}{|C|} \sum_o \Pr(o \mid s) \cdot E[C_o] $$

这里 $o$ 遍历所有 $3^l$ 种可能的观测串（每位 $0/1/?$）。

---

问题简化

注意 $E[C]$ 依赖于真正的答案在 $C$ 中，但不知道是哪一个。
我们实际需要的是：对于每个 $t \in S$，从初始状态 $S$ 开始，假设答案就是 $t$ 的期望成本 $F(t)$。

设 $F(C, t)$ 表示当前候选集为 $C$，且真实答案为 $t \in C$ 时的期望额外成本。

则：

$$F(C, t) = 1 + \sum_o \Pr(o \mid t) \cdot F(C_o, t) $$

边界：若 $C = \{t\}$，则 $F(C, t) = 0$。

我们要求的就是 $F(S, t)$ 对于每个 $t \in S$。

---

算法实现

由于 $l \leq 15$，我们可以用位集表示候选集，但 $n \leq 2^l$ 可能很大，不能直接枚举所有子集。

但注意：观测只依赖于字符串间的区别。我们可以用"区分集"的思想：

对于两个串 $a, b \in S$，它们在第 $i$ 位不同。要区分它们，需要在第 $i$ 位获得真实信息（概率 $p_i$）。

实际上，这是一个随机过程直到某个停止条件的问题，可以用包含-排除原理或高维DP解决。

---

更高效的解法

设 $T$ 是 $S$ 的子集，定义 $q(T)$ 为一次观测不能区分 $T$ 中任意两个串的概率。

那么 $T$ 中的串在观测后仍然全部在同一个候选集中的概率是：

$$\sum_o \min_{t \in T} \Pr(o \mid t)$$

但实际上更简单：不能区分 $T$ 意味着对于每个位置 $i$，要么所有串在该位相同且观测为 ?，要么观测为该位的值。

经过推导（见样例解释），可以得到：

对于固定答案串 $t$，期望游戏币数为：

$$E_t = \sum_{T \subseteq S,\ t \in T} (-1)^{|T|-1} \frac{1}{1 - P_T} $$

其中 $P_T$ 是一次观测后 $T$ 中所有串仍然无法区分的概率。

---

概率 $P_T$ 的计算

$T$ 中所有串无法区分，当且仅当对于每个位置 $i$：

• 如果 $T$ 中所有串在第 $i$ 位相同，则观测可以是该位值或 ?
• 如果 $T$ 中串在第 $i$ 位有不同值，则观测必须是 ?

所以：

$$P_T = \prod_{i=0}^{l-1} \begin{cases} 1 & \text{if } T \text{ 在位置 } i \text{ 有不同值} \\ p_i + (1-p_i) = 1 & \text{实际上这里需要修正} \end{cases} $$

正确公式： 设 $b_i(T) = 1$ 如果 $T$ 中所有串在第 $i$ 位相同，否则为 0。

那么：

$$P_T = \prod_{i=0}^{l-1} \begin{cases} 1 & \text{if } b_i(T) = 0 \ (\text{有不同值，必须观测为?}) \\ 1 & \text{if } b_i(T) = 1 \ (\text{相同，观测任意}) \end{cases} \ \text{❌ 这不对} $$

重新推导：

对于位置 $i$：

• 如果 $T$ 中所有串在第 $i$ 位都是 $v$，那么观测可以是 $v$（概率 $p_i$）或 ?（概率 $1-p_i$），所以该位贡献因子 $1$。
• 如果 $T$ 中串在第 $i$ 位有 $0$ 和 $1$，那么观测必须是 ?（概率 $1-p_i$），所以贡献因子 $1-p_i$。

因此：

$$P_T = \prod_{i=0}^{l-1} \begin{cases} 1 & \text{if } T \text{ 在位置 } i \text{ 上值都相同} \\ 1-p_i & \text{if } T \text{ 在位置 } i \text{ 上有不同值} \end{cases} $$

---

最终算法

1. 预处理 $2^n$ 个子集 $T$ 的 $P_T$（但 $n$ 可能很大，不过 $l$ 小，可以用位运算枚举）。
2. 实际上我们不需要枚举所有 $T \subseteq S$，只需要枚举 $T$ 在位置上的模式。
3. 用包含-排除计算每个 $t$ 的期望：$$E_t = \sum_{T \ni t} (-1)^{|T|-1} \frac{1}{1-P_T}$$ 对 $998244353$ 取模。

由于 $n$ 可能达到 $2^l$，直接枚举 $2^n$ 不可行。需要利用 $l$ 小的特点，按位置集合进行DP。

---

复杂度优化

我们注意到 $P_T$ 只依赖于 $T$ 在每个位置上的取值情况（是否全相同）。
可以用 $O(4^l)$ 的DP计算所有模式的出现次数和符号和。

具体步骤：

1. 将每个串 $s$ 用整数 $mask[s] \in [0, 2^l)$ 表示。
2. 对于每个位置子集 $A \subseteq [l]$，定义 $f[A]$ 为满足"在位置集 $A$ 上所有串相同，在位置集 $\overline{A}$ 上有不同值"的 $T$ 的带符号和。
3. 用高维前缀和计算 $f[A]$。
4. 则 $E_t$ 可以表示为对 $A$ 的求和。

这样复杂度为 $O(4^l + n \cdot 2^l)$，在 $l \leq 15$ 时可行。

---

代码框架

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int modpow(int a, int e) {
    int res = 1;
    while (e) {
        if (e & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int l, n;
        cin >> l >> n;
        vector<int> p(l);
        for (int i = 0; i < l; i++) {
            int c;
            cin >> c;
            p[i] = 1LL * c * modpow(10000, MOD-2) % MOD;
        }
        
        vector<int> s(n);
        for (int i = 0; i < n; i++) {
            string str;
            cin >> str;
            int mask = 0;
            for (char ch : str) {
                mask = (mask << 1) | (ch - '0');
            }
            s[i] = mask;
        }
        
        // 这里实现上述DP算法
        // 由于代码较长，只给出框架
        
        vector<int> E(n, 0);
        // 计算每个s[i]的期望值存入E[i]
        
        for (int i = 0; i < n; i++) {
            cout << E[i] << "\n";
        }
    }
    return 0;
}

---

总结

本题的核心是：

1. 将问题建模为随机过程直到候选集大小为 1
2. 利用包含-排除原理将期望表示为子集和
3. 利用 $l$ 小的特点，通过位运算和DP高效计算
4. 注意模运算和概率的转换