CF1033F Boolean Computer

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{matrix} 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 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \end{matrix} $$ 要构建一个“数字门”，需要将 $w$ 个比特门组装成一个数组。一个“数字门”以两个 $w$ 位整数 $x_1$ 和 $x_2$ 作为输入。该“数字门”会将整数拆分为 $w$ 个比特，并将每个输入的第 $i$ 位比特送入第 $i$ 个比特门。最后，将输出的比特重新组合成一个输出数值。 例如，对于 $4$ 位计算机，可以有一个“数字门” "AXoA"（与、异或、非或、与）。对于两个输入 $13 = 1101_2$ 和 $10 = 1010_2$，其输出为 $12 = 1100_2$，因为 $1$ 与 $1$ 得 $1$，$1$ 异或 $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$ 行，每行包含一个长度为 $w$ 的字符串 $g_j$，描述一个数字门。每个字符都是 “A”、 “O”、 “X”、 “a”、 “o”、 “x” 之一。

输出 $m$ 行。第 $i$ 行输出第 $i$ 个门输出为零的有序变量对的数量。

在第一个测试用例中，输入的二进制数为 $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$。 由 ChatGPT 4.1 翻译