← 返回题目列表

Codeforces · 1033/F

F. 布尔计算机

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

Alice 有一台运行 $$$w$$$ 位整数的计算机。计算机有 $$$n$$$ 寄存器来存储值。寄存器的当前内容以数组 $$$a_1, a_2, \ldots, a_n$$$ 的形式给出。

计算机使用所谓的“数字门”来操纵这些数据。每个“数字门”将两个寄存器作为输入,并计算存储在这些寄存器中的两个值的函数。请注意,您可以使用相同的寄存器作为两个输入。

每个“数字门”都是由位门组装而成。位门有六种类型:AND、OR、XOR、NOT AND、NOT OR 和 NOT XOR,分别表示为“A”、“O”、“X”、“a”、“o”、“x”。每个位门采用两位作为输入。给定输入位 $$$b_1$$$、$$$b_2$$$ 时,其输出如下:

$$$\begin{矩阵} b_1 & b_2 & A & O & X & a & o & x \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{矩阵}$$$

要构建“数字门”,需要使用 $$$w$$$ 位门并将它们组装成一个数组。 “数字门”采用两个 $$$w$$$ 位整数 $$$x_1$$$ 和 $$$x_2$$$ 作为输入。 “数字门”将整数分成 $$$w$$$ 位,并将每个输入的第 $$$i$$$ 位馈送到第 $$$i$$$ 位门。之后,它再次组合结果位以形成输出字。

例如,对于 $$$4$$$ 位计算机,我们可能有一个“数字门”“AXoA”(AND、XOR、NOT OR、AND)。对于两个输入,$$$13 = 1101_2$$$ 和 $$$10 = 1010_2$$$,这将返回 $$$12 = 1100_2$$$,因为 $$$1$$$ 和 $$$1$$$ 是 $$$1$$$,$$$1$$$ xor $$$0$$$ 是 $$$1$$$,而不是 ($$$0$$$ 或$$$1$$$) 是 $$$0$$$,最后 $$$1$$$ 和 $$$0$$$ 是 $$$0$$$。

给你一个$$$m$$$“数字门”的描述。对于每个门,您的目标是报告“数字门”输出数字 $$$0$$$ 的寄存器对的数量。换句话说,找到有序对 $$$(i,j)$$$ 的数量,其中 $$$1 \leq i,j \leq n$$$,使得 $$$w_k(a_i, a_j) = 0$$$,其中 $$$w_k$$$ 是由第 $$$k$$$ 个“数字门”计算的函数。

输入

第一行包含三个整数:$$$w$$$、$$$n$$$ 和 $$$m~(1 \leq w \leq 12, 1 \leq n \leq 3\cdot 10^4, 1 \leq m \leq 5\cdot 10^4)$$$ — 字大小、变量数量和门数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \leq a_i < 2^w)$$$ - 存储在寄存器中的变量值。

接下来的 $$$m$$$ 行包含一个字符串 $$$g_j~(|g_j| = w)$$$ 以及单个门的描述。 $$$g_j$$$ 的每个字符都是“A”、“O”、“X”、“a”、“o”、“x”之一。

输出

打印 $$$m$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 门返回零的有序变量对的数量。

示例

输入 #1

4 3 1
13 10 6
AXoA

输出 #1

3

输入 #2

1 7 6
0 1 1 0 1 0 0
A
O
X
a
o
x

输出 #2

40
16
25
9
33
24

输入 #3

6 2 4
47 12
AOXaox
AAaaAA
xxxxxx
XXXXXX

输出 #3

2
3
0
2

输入#4

2 2 2
2 0
xO
Ox

输出#4

2
0

注意

在第一个测试用例中,二进制输入为 $$$1101$$$、$$$1010$$$、$$$0110$$$。返回 $$$0$$$ 的对是 $$$(13, 6)$$$、$$$(6, 13)$$$ 和 $$$(6, 6)$$$。正如问题陈述中已经提到的,$$$13 \oplus 10 = 10 \oplus 13 = 12$$$。其他对是 $$$13 \oplus 13 = 11$$$、$$$10 \oplus 10 = 8$$$ 和 $$$10 \oplus 6 = 6 \oplus 10 = 4$$$。