AT_joi2018ho_e 毒蛇の脱走 (Snake Escaping)

在 JOI 研究所里饲养着 $2^L$ 条毒蛇，每条毒蛇编号为 $0, 1, \ldots, 2^L - 1$。每条毒蛇的身体从头部开始被分为 $L$ 个部分，每个部分要么是蓝色，要么是红色。对于毒蛇 $i$，将 $i$ 用二进制表示为 $i = \sum_{k=1}^{L} c_k 2^{L-k}$（$0 \leq c_k \leq 1$）时： - 若 $c_k = 0$，则毒蛇 $i$ 从头部数第 $k$ 个部分为蓝色； - 若 $c_k = 1$，则毒蛇 $i$ 从头部数第 $k$ 个部分为红色。 每条毒蛇都有一个称为“毒性”的整数值，范围在 $0$ 到 $9$ 之间。给定一个由 `0` 到 `9` 组成、长度为 $2^L$ 的字符串 $S$，第 $i$ 个字符（$1 \leq i \leq 2^L$）表示毒蛇 $i-1$ 的毒性。 毒蛇们行动迅速，经常会从 JOI 研究所逃脱。每当有毒蛇逃脱时，周边居民会向研究所投诉。 你将得到 $Q$ 天的投诉信息。第 $d$ 天（$1 \leq d \leq Q$）的投诉信息用一个由 `0`、`1`、`?` 组成、长度为 $L$ 的字符串 $T_d$ 表示： - $T_d$ 的第 $j$ 个字符（$1 \leq j \leq L$）为 `0` 时，表示第 $d$ 天逃脱的所有毒蛇从头部数第 $j$ 个部分为蓝色； - $T_d$ 的第 $j$ 个字符为 `1` 时，表示第 $d$ 天逃脱的所有毒蛇从头部数第 $j$ 个部分为红色； - $T_d$ 的第 $j$ 个字符为 `?` 时，表示居民未能提供该部分的信息。 所有投诉信息都是准确的。当天逃脱的毒蛇会被研究所工作人员当天抓回，之后不会再次逃脱。 为了评估毒蛇逃脱带来的风险，JOI 研究所的 K 理事长希望知道每天可能逃脱的毒蛇的毒性总和。你的任务是，根据 $Q$ 天的投诉信息，编写程序计算每天可能逃脱的毒蛇的毒性总和。

从标准输入读取以下内容。 - 第 $1$ 行包含两个整数 $L, Q$，用空格分隔，分别表示毒蛇身体部分的数量和投诉天数。 - 第 $2$ 行包含一个长度为 $2^L$ 的字符串 $S$，表示每条毒蛇的毒性。 - 接下来的 $Q$ 行，第 $d$ 行（$1 \leq d \leq Q$）包含一个长度为 $L$ 的字符串 $T_d$，表示第 $d$ 天的投诉信息。

输出 $Q$ 行。第 $d$ 行输出第 $d$ 天可能逃脱的毒蛇的毒性总和。

## 任务 给定毒蛇毒性字符串 $S$ 和 $Q$ 天的投诉信息，计算每天可能逃脱的毒蛇的毒性总和。 注意内存限制较小。 ## 限制 所有输入数据满足以下条件： - $1 \leq L \leq 20$。 - $1 \leq Q \leq 1\,000\,000$。 - $S$ 是长度为 $2^L$ 的字符串。 - $S$ 仅包含 `0` 到 `9` 的字符。 - $T_d$ 是长度为 $L$ 的字符串（$1 \leq d \leq Q$）。 - $T_d$ 仅包含 `0`、`1`、`?` 字符（$1 \leq d \leq Q$）。 ## 子任务 ### 子任务 1 [5 分] 满足以下条件： - $L \leq 10$。 - $Q \leq 1\,000$。 ### 子任务 2 [7 分] - 满足 $L \leq 10$。 ### 子任务 3 [10 分] - 满足 $L \leq 13$。 ### 子任务 4 [53 分] - 满足 $Q \leq 50\,000$。 ### 子任务 5 [25 分] - 无额外限制。 ## 样例解释 1 在此输入样例中，$L = 3$。毒蛇被分为 $3$ 个部分，共有 $2^3 = 8$ 条毒蛇。投诉持续 $5$ 天。 - 第 $1$ 天可能逃脱的毒蛇只有毒蛇 $0$，毒性总和为 $1$。 - 第 $2$ 天可能逃脱的毒蛇为毒蛇 $0, 1, 2, 3$，毒性总和为 $10$。 - 第 $3$ 天可能逃脱的毒蛇为毒蛇 $4, 6$，毒性总和为 $12$。 - 第 $4$ 天可能逃脱的毒蛇为毒蛇 $3, 7$，毒性总和为 $12$。 - 第 $5$ 天可能逃脱的毒蛇为毒蛇 $0, 1, 2, 3, 4, 5, 6, 7$，毒性总和为 $36$。 由 ChatGPT 4.1 翻译