4363: 「JOI 2018 Final」毒蛇越狱

JOI 研究所有 $2^L$ 条毒蛇，这些毒蛇编号为 $0, 1, \dots, 2^L-1$。每条毒蛇从头到尾被分成 $L$ 段，每段的颜色为蓝、红中的一种。对于毒蛇 $i$，令 $i=\sum_{k=1}^L c_k\times 2^{L-k}, (0≤c_k≤1)$ 为 $i$ 的二进制展开，若 $c_k=0$，则毒蛇 $i$ 的第 $k$ 段是蓝色的，否则是红色的。 每条毒蛇有一个 $0$ 到 $9$ 的整数表示它的毒性。给出一个长度为 $2^L$ 的字符串，其中字符均在 `0` 到 `9` 的范围内，第 $i$ 位字符表示第 $i-1$ 条毒蛇的毒性。 这些毒蛇移动速度非常快，所以他们经常从 JOI 研究所逃跑，因此，研究所附近的住户投诉时常看见从研究所逃出的毒蛇。 研究所整理出了 $Q$ 天来住户的举报清单，第 $d$ 天的收到的举报是一个长度为 $L$ 且仅包含 `0`, `1`, `?` 的字符串 $T_d$。 如果 $T_d$ 的第 $j$ 个字符为 `0`，这意味着逃跑毒蛇的第 $j$ 段是蓝色的； 如果 $T_d$ 的第 $j$ 个字符为 `1`，这意味着逃跑毒蛇的第 $j$ 段是红色的； 如果 $T_d$ 的第 $j$ 个字符为 `?`，这意味着没有人注意到逃跑毒蛇的第 $j$ 段是什么颜色的。 研究所保证投诉均为准确的信息，并且根据这些信息，JOI 研究所每天会将逃跑的毒蛇全部捕获回来，因此会发生同一条毒蛇在不同日子逃跑的情况。 为了估计逃跑的毒蛇的风险，JOI 实验室的执行主任 K 教授想知道所有可能逃跑的毒蛇的毒性之和。你的任务是编写一个程序，给出 $Q$ 天的投诉清单，计算每天可能从实验室逃跑的毒蛇的毒性之和。 **注意本题空间限制较小。**

从标准输入中读取数据。 第一行包括两个整数 $L, Q$，表示毒蛇的颜色段数与收到投诉的天数。 第二行包括一个长度为 $2^L$ 的字符串 $S$，描述毒蛇的毒性。 接下来 $Q$ 行，第 $d+2$ 行有长为 $L$ 的字符串，表示 $T_d$。

输出数据到标准输出中。 输出共 $Q$ 行，每行一个整数，表示所有可能逃跑的毒蛇的毒性之和。

3 5
12345678
000
0??
1?0
?11
???

1
10
12
12
36