P12020 CF1033F 加强版

定义一种二元位运算为 $\odot$ ，运算数均在区间 $[0,2^w)$ 内，他使用数字门进行运算，运算法则由一个长度为 $w$ 的字符串构成，设为 $s$，$s$ 仅包含 $\texttt{A,O,X,a,o,x}$，分别表示 与，或，异或，与非，或非，同或，表示每一位的运算法则。以下是这些位运算的真值表，$p,q$ 为参与运算的两个数： $$\begin{matrix}\texttt{p\ q\ A\ O\ X\ a\ o\ x}\\\texttt{0\ 0\ 0\ 0\ 0\ 1\ 1\ 1}\\\texttt{0\ 1\ 0\ 1\ 1\ 1\ 0\ 0}\\\texttt{1\ 0\ 0\ 1\ 1\ 1\ 0\ 0}\\\texttt{1\ 1\ 1\ 1\ 0\ 0\ 0\ 1}\end{matrix}$$ 具体地，$x\odot y \ (s) =z$ 的运算方式如下： + $z$ 的二进制的**从高到低**第 $i$ 位的结果是 $x$ 和 $y$ 的第 $i$ 位通过 $s_i$ 对应的运算得到的。 给定 $n$ 个 $[0,2^w)$ 中的数 $a_1,a_2,\cdots ,a_n$ 和 $q$ 组询问，每次询问给定门运算的运算法则 $s$，询问有多少对**有序对** $(x,y)$ 满足 $a_x \odot a_y = z$（注意 $x$ 可以等于 $y$）。

第一行四个正整数 $T,w,n,q$，分别表示测试点编号，运算法则长度，$a$ 序列长度和询问数量。 第二行 $n$ 个整数，表示 $a_1,a_2,\dots,a_n$。 接下来 $q$ 行，每行一个字符串 $s$ 和一个非负整数 $z$。

对于每个询问，输出一个非负整数，表示符合要求的有序对 $(x,y)$ 数量。

| 测试点编号 | $w\leq$ | $n\leq$ | $q\leq$ | 特殊性质 | | ----------- | ------- | ------- | ------------- | -------------------------------------- | | $1\sim 3$ | $16$ | $100$ | $10$ | 无 | | $4\sim 5$ | $8$ | $10^5$ | $10$ | 无 | | $6\sim9$ | $10$ | $10^5$ | $10^4$ | 无 | | $10\sim 12$ | $11$ | $10^5$ | $3\times10^4$ | 无 | | $13\sim14$ | $12$ | $10^5$ | $5\times10^4$ | 无 | | $15\sim16$ | $13$ | $10^5$ | $7\times10^4$ | 无 | | $17\sim19$ | $14$ | $10^5$ | $10^5$ | 无 | | $20\sim21$ | $16$ | $10^5$ | $10^5$ | $s_i$ 仅包含 $\texttt{O,a,x}$，$z_i=0$ | | $22\sim25$ | $16$ | $10^5$ | $10^5$ | 无 | 对于 $100\%$ 的数据：$1\leq w\leq 16$，$1\leq n\leq10^5$，$1\leq q\leq 10^5$，$0\leq z_i,a_i