#2351. 「JOI 2018 Final」毒蛇越狱

内存限制:64 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

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 的字符串,其中字符均在 09 的范围内,第 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 行,每行一个整数,表示所有可能逃跑的毒蛇的毒性之和。

样例

样例输入 1
3 5
12345678
000
0??
1?0
?11
???
样例输出 1
1
10
12
12
36
样例说明 1

样例中 L=3 ,共有 2^3=8 条毒蛇,每条毒蛇分成三段,共有 5 天收到投诉。

第一天:逃跑的毒蛇只可能是第 0 条毒蛇,毒性之和为 1
第二天:逃跑的毒蛇只可能是第 0, 1, 2, 3 条毒蛇,毒性之和为 10
第三天:逃跑的毒蛇只可能是第 4, 6 条毒蛇,毒性之和为 12
第四天:逃跑的毒蛇只可能是第 3, 7 条毒蛇,毒性之和为 12
第五天:逃跑的毒蛇只可能是第 0, 1, 2, 3, 4, 5, 6, 7 条毒蛇,毒性之和为 36

样例输入 2
4 8
3141592653589793
0101
?01?
??1?
?0??
1?00
01?1
??10
????
样例输出 2
9
18
38
30
14
15
20
80

数据范围与提示

Subtask # 分值 L Q
1 5 L\le 10 Q\le 1000
2 7 -
3 10 L\le 13
4 53 - Q\le 5\times 10^4
5 25 -

对于所有输入数据,有 1≤L≤20, 1≤Q≤10^6