#P7326. 「MCOI-07」Dream and Evaluation

「MCOI-07」Dream and Evaluation

题目描述

George 在学位运算。他编了一个位运算表达式,但是他不会高效计算这个表达式的值,于是他找 Dream 帮他计算。
George 的表达式有 6464 个 01 变量,分别编号为 006363。他提供了该表达式的后缀表示法
后缀表示法里可能含有以下符号:

  • 0,1,,630,1,\dots,63,代表对应变量
  • !&|^,代表对应位运算

现在 Dream 有 mm 个情况。每一个情况固定所有 6464 个变量的值。他需要你对每一个情况计算给定表达式的值。
为了方便输入,这些情况进行压缩。定义 ai,ja_{i,j} 为第 ii 情况里的第 jj 变量值,其中 ai,j{0,1}a_{i,j}\in\{0,1\};他会给你

bi=j=063ai,j2jb_i=\sum_{j=0}^{63}a_{i,j}2^j

可以证明,如果 0bi<2640\le b_i<2^{64},则 bib_i 唯一对应一组 ai,0,ai,1,,ai,63a_{i,0},a_{i,1},\dots,a_{i,63}

输入格式

第一行一个正整数 nn,表示后缀表示法的长度。
接下来一行 nn 个符号,表示 George 的表达式。
接下来一行一个正整数 mm
接下来一行 mm 个整数,依次代表 b1,b2,,bmb_1,b_2,\dots,b_m

输出格式

输出 mm 个 01 字符,其中第 ii 输出字符代表第 ii 情况时,表达式的值。

8
0 1 ^ 2 3 ! & |
7
1 9 1 9 8 1 0
1111010
23
0 ! ! 3 0 3 ^ ^ 3 | & 1 ! ^ 2 0 ! 3 ^ ! ^ ! ^
20
11 10 4 8 13 7 2 5 11 9 16 15 6 9 7 8 15 0 2 10
00110011010101011010

提示

样例 1 解释

如果 x=1x=1,则变量 0011,其余变量为 00
如果 x=9x=9,则仅变量 003311

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(7 pts):n,m103n,m\le10^3
  • Subtask 2(11 pts):bi[0,281]b_i\in[0,2^{8}-1]
  • Subtask 3(41 pts):n,m5×104n,m\le5\times10^4
  • Subtask 4(41 pts):没有额外限制。

对于所有数据,1n,m1051\le n,m\le10^50bi<2640\le b_i<2^{64}