[JOI2018] Snake Escaping

JOI 实验室有 $2^L$ 条毒蛇。蛇的编号为 $0,1,\cdots,2^L−1$。每条蛇从头到尾分为 $L$ 个部分。每个部分的颜色是蓝色或红色。 对于毒蛇 $i$，令 $i = \sum_{k=1}^{L} c_k2^{L-k}$（$0 \leq c_k \leq 1$）为 $i$ 的二进制表达式。那么， - 如果 $c_k=0$，毒蛇 $i$ 从头开始的第 $k$ 部分的颜色是蓝色， - 如果 $c_k=1$，毒蛇 $i$ 从头开始的第 $k$ 部分的颜色是红色。 每条毒蛇都有一个 $0$ 到 $9$ 之间的整数，包括 $0$ 和 $9$，为毒性。给出一个由 $\texttt{0,1,2,3,4,5,6,7,8,9}$ 组成的长度为 $2^L$ 的字符串 $S$。第 $i$ 个字符（$1 \leq i \leq 2^L$）是毒蛇 $i−1$ 的毒性。由于毒蛇行动迅速，所以经常从 JOI 实验室逃走。住在实验室附近的人向 JOI 实验室投诉，他们看到毒蛇从实验室逃逸。您将收到 $Q$ 天的投诉清单。 第 $d$ 天的投诉（$1 \leq d \leq Q$）是一个长度为 $L$ 的字符串 $T_d$，由 $\texttt{0,1,?}$ 组成。 - 如果 $T_d$ 的第 $j$ 个字符（$1 \leq j ≤ L$）为 $\texttt{0}$，这意味着第 $d$ 天从实验室逃出的每条毒蛇的第 $j$ 个部分是蓝色的， - 如果 $T_d$ 的第 $j$ 个字符（$1 \leq j \leq L$）为 $\texttt{1}$，这意味着第 $d$ 天从实验室逃出的每条毒蛇的第 $j$ 部分是红色的，并且 - 如果 $T_d$ 的第 $j$ 个字符（$1 \leq j \leq L$）为 $\texttt{?}$，这意味着人们没有提供关于第 $d$ 天从实验室逃逸的毒蛇的第 $j$ 部分的信息。 所有的投诉都是准确的信息。所有从实验室逃逸的毒蛇都在同一天被 JOI 实验室的工作人员收留。可能发生同一条蛇在不同的日子逃脱。 JOI 实验室执行主任 K 教授为了估计毒蛇逃逸的风险，想知道可能逃出实验室的毒蛇的毒性总和。 你的任务是编写一个程序，根据 $Q$ 天的投诉列表，计算每天可能从实验室逃逸的蛇的毒性总和。 现给定描述毒蛇毒性的字符串 $S$ 和 $Q$ 天的投诉列表，请编写一个程序来计算每天可能从实验室逃逸的蛇的毒性总和。 请注意，此任务的内存限制很小。

第一行包含两个空格分隔的整数 $L$，$Q$，分别是每条毒蛇的部位数和投诉天数。第二行包含长度为 $2^L$ 的字符串 $S$，描述了毒蛇的毒性。后面 $Q$ 行的第 $d$ 行包含一个长度为 $L$ 的字符串 $T_d$，为第 $d$ 天的投诉。

共 $Q$ 行，第 $d$ 行应包含一个整数，即第 $d$ 天可能从实验室逃逸的蛇的毒性总和。

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

1
10
12
12
36

4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????

9
18
38
30
14
15
20
80

#### 数据规模与约定 对于 $100 \%$ 的数据，$1 \leq L \leq 20$，$1 \leq Q \leq 10^6$，$S$ 是长度为 $2^L$ 的字符串，字符串 $S$ 由 $\texttt{0,1,2,3,4,5,6,7,8,9}$ 组成，$T_d$ 是长度为 $L$（$1 \leq d \leq Q$）的字符串，字符串 $T_d$ 由 $\texttt{0,1,?}$（$1 \leq d \leq Q$）组成。 - Subtask $1$（$5$ points）：$L \leq 10$，$Q \leq 1000$。 - Subtask $2$（$7$ points）：$L \leq 10$。 - Subtask $3$（$10$ points）：$L \leq 13$。 - Subtask $4$（$53$ points）：$Q \leq 5000$。 - Subtask $5$（$25$ points）：没有额外的限制。 #### 样例说明 **对于样例 $1$**：$L=3$，共 $2^3=8$条毒蛇，它们中的每一条都分为 $3$ 个部分。 投诉时间为 $5$ 天。 - 第一天，可能逃出实验室的毒蛇只有毒蛇 $0$。毒性总和为 $1$。 - 第二天，可能从实验室逃逸的毒蛇是毒蛇 $0,1,2,3$。毒性总和为 $10$。 - 第三天，可能从实验室逃逸的毒蛇是毒蛇 $4,6$。毒性总和为 $12$。 - 第四天，可能从实验室逃逸的毒蛇是毒蛇 $3,7$。毒性总和是 $12$。 - 第五天，可能从实验室逃逸的毒蛇是毒蛇 $0,1,2,3,4,5,6,7$。毒性总和为 $36$。 #### 题目说明： 来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T5：Snake Escaping](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t5-en.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。