分数: 6 点
问题陈述
有两个盒子 A 和 B 包含介于之间的整数的球 上面写着 0 和 2^N-1 。盒子 A 包含 A_i 带有整数的球 i (0 \leq i \lt 2^N)和盒子 B 包含 B_i 带有整数的球 i (0 \leq i \lt 2^N)。所有球都是可区分的。
考虑从每个盒子中拾取一个球 A 和盒子 B。其中(盒子内的球数 A) \times (盒子里的球数 B)这样做的方法,让 f(x, y) 是满足以下条件的数量。
- 这里我们用 \mathrm{popcount}(x) 数量 1s 的二进制表示法 x.
让 a 和 b 是写在球上的整数 分别为 A 和 B。然后,按位或 a 和 b is x,和 \mathrm{popcount}(a) + \mathrm{popcount}(b) is y.
给定了序列 X 和 Y 长度 Q 每个。计算 f(X_i, Y_i) 模数 998244353 对于每个 i (1 \leq i \leq Q).
约束
- 1 \leq N \leq 17
- 1 \leq Q \leq 10^5
- 0 \leq A_i \lt 998244353 (0 \leq i \lt 2^N)
- 0 \leq B_i \lt 998244353 (0 \leq i \lt 2^N)
- 0 \leq X_i \lt 2^N (1 \leq i \leq Q)
- 0 \leq Y_i \leq 2N (1 \leq i \leq Q)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q
A_0 A_1 \dots A_{2^N-1}
B_0 B_1 \dots B_{2^N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
输出
打印 Q 行。的 i- 第行应包含 f(X_i,Y_i) \bmod{998244353}.
示例输入 1
2 3 3 1 4 1 5 9 2 6 1 1 3 2 2 0
示例输出 1
32 61 0
- 对于 x = 1 和 y = 1,对应的对 (a, b) 是 (a,b) = (0, 1), (1, 0)。因此,所求的数为 A_0 \times B_1 + A_1 \times B_0 = 32.
- 对于 x = 3 和 y = 2,对应的对 (a, b) 是 (a,b) = (0,3),(1,2),(2,1),(0,3)。因此,所求的数为 A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61.
- 对于 x = 2 和 y = 0,没有对应的对 (a, b)。因此,所求的数为 0.
示例输入 2
1 1 0 0 1 2 1 1
示例输出 2
0
一个或多个方框可能是空的。