#CW64. 毒蛇越狱(snakes)

毒蛇越狱(snakes)

题目描述

共有 2L2^L 条蛇,编号为 0,1,…,2L−10,1,\dots,2^L-1。把编号写成恰好 LL 位的二进制串,必要时在左侧补前导零。给定一个长度为 2L2^L 的数字字符串 SS,其中第 ii 个字符记录编号为 i−1i-1 的蛇的毒性数值;字符是一个十进制数字,因此毒性取值在 00 到 99 之间。

每天会出现一个长度为 LL 的模式串,只包含 0、1 和 ?。模式中的 0 或 1 要求对应二进制位必须相同,? 表示这一位可以是任意值。各个 ? 彼此独立,所以一个模式通常会匹配多条蛇。请计算所有匹配蛇的毒性之和。每个询问都独立使用同一条字符串 SS,询问之间不修改任何毒性。

输入格式

从 snakes.in 文件中读入。

第一行给出 LL 和询问数 QQ。第二行给出长度恰为 2L2^L 的字符串 SS;从左到右的字符依次对应蛇编号 00 到 2L−12^L-1。随后 QQ 行每行给出一个长度为 LL 的模式串,且只含有 0、1 和 ?。

输出格式

从 snakes.out 文件中输出。

输出 QQ 行,按照询问顺序,每行一个整数,表示匹配该模式的所有蛇的毒性总和。

样例 1 输入

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

样例 1 输出

1
10
12
12
36

样例 1 解释

  • 000 只匹配编号 00,毒性为 11;
  • 0?? 匹配编号 0∼30\sim 3,毒性之和为 1+2+3+4=101+2+3+4=10;
  • 1?0 匹配编号 1002=4100_2=4 和 1102=6110_2=6,毒性之和为 5+7=125+7=12;
  • ?11 匹配编号 0112=3011_2=3 和 1112=7111_2=7,毒性之和为 4+8=124+8=12;
  • ??? 匹配全部编号,毒性之和为 3636。

样例 2 输入

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

样例 2 输出

9
18
38
30
14
15
20
80

数据范围

对全部数据,1≤L≤201\le L\le 20,1≤Q≤1061\le Q\le 10^6,SS 的长度为 2L2^L。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 5 11 L≤10L\le 10 且 Q≤1000Q\le 1000
2 7 2∼32\sim 3 L≤10L\le 10
3 10 4∼54\sim 5 L≤13L\le 13
4 53 6∼156\sim 15 Q≤5000Q\le 5000
5 25 16∼2016\sim 20 无额外限制