← 返回题目列表

AtCoder · joi2018ho_e

E. 蛇逃跑

中文机器翻译题面 查看原题

配点: 100 点

在 JOI 学院 2^L 我有两条毒蛇,每条都有一个 它的编号为 0, 1, \ldots, 2^L - 1 。所有的毒蛇都是从头开始的 它分为 L 部分,每个部分都是蓝色或红色。毒蛇 对于 i ,i 的 2 以十进制表示 i = \sum_{k = 1}^{L} c_k 2^{L - k} (0 \leqq c_k \leqq 1),

  • c_k = 0 如果是毒蛇 从 i 开始计数 第 k 部分是蓝色的, 第
  • c_k = 1 如果是毒蛇 从 i 开始计数 第 k 部分是红色的。

每条毒蛇都称为毒蛇 0 以上 9 以下整数值是固定的。 长度由0,1,2,3,4,5,6,7,8,9 组成 2^L 字符串 给出 S ,其 i 文字目 (1 \leqq i \leqq 2^L) 是一条毒蛇 代表 i - 1 的毒性。

由于毒蛇行动速度快,它们经常从JOI学院逃脱。 JOI研究所收到附近居民的投诉,称他们目睹了毒蛇逃跑。

为了你,Q 给出了天数的投诉信息。 已向d 日目 (1 \leqq d \leqq Q提出投诉) 表示为 0,1,? 组成 L 字符串 给出 T_d ,

  • T_d 的 j 文字目 (1 \leqq j \leqq L)是 对于 0 ,d 从当天逃脱的所有毒蛇的头数开始 代表第 j 部分为蓝色, 表示第
  • T_d 的 j 文字目 (1 \leqq j \leqq L)是 对于 1 ,d 从当天逃脱的所有毒蛇的头数开始 代表第 j 部分为红色,
  • T_d 的 j 文字目 (1 \leqq j \leqq L)是 对于 ? ,d 从当天逃脱的毒蛇头开始算 第 j 部分表示周边居民未提供任何信息。

所有投诉均为准确信息。 JOI研究所的工作人员在同一天捕获了逃跑的毒蛇。被捕获的毒蛇有可能第二天再次逃脱。

为了估计毒蛇逃逸的风险,JOI研究所的K主任想知道可能逃逸的毒蛇的总毒性。你的工作是Q 目的是创建一个程序,根据一段时间内的投诉信息,计算出每天可能逃逸的毒蛇的总毒液量。

課題

代表毒蛇毒性的字符串 S 和Q 给定每天的投诉信息,编写一个程序,计算每天可能逃逸的毒蛇的总毒液量。

请注意,内存限制很小。


入力

从标准输入读取以下输入。

  • 1 行包含一个整数 L, Q 以空格作为分隔符。这些又代表了毒蛇部位的数量和收到投诉的天数。
  • 2 长度是 写入 2^L 字符串 给出 S 。这根绳子代表蛇的毒液。
  • 继续 Q 行 d 行目 (1 \leqq d \leqq Q) 的长度 写入 L 字符串 给出 T_d 。这个字符串是 d 代表当天的投诉。

出力

到标准输出 在 Q 行。d 行中,d 打印一个整数,表示第一天可能逃脱的毒蛇的总毒液。


制限

所有输入数据满足以下条件。

  • 1 \leqq L \leqq 20.
  • 1 \leqq Q \leqq 1\,000\,000.
  • S 是长度 它是一个 2^L 字符串。 它由
  • 文字列 S 为 0,1,2,3,4,5,6,7,8,9 组成。 它是一个字符串
  • T_d 是长度 它是一个 L ( 组成为1 \leqq d \leqq Q).
  • 文字列 T_d 为 0,1,? (1 \leqq d \leqq Q).

小課題

小課題 1 [5 点]

满足以下条件。

  • L \leqq 10.
  • Q \leqq 1 000.

小課題 2 [7 点]

  • L \leqq 10 很满意。

小課題 3 [10 点]

  • L \leqq 13 很满意。

小課題 4 [53 点]

  • Q \leqq 50 000 很满意。

小課題 5 [25 点]

  • 没有其他限制。

入力例 1

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

出力例 1

1
10
12
12
36

在此输入示例中,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 。

入力例 2

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

出力例 2

9
18
38
30
14
15
20
80