← 返回题目列表

AtCoder · past202209_o

O. 选择两个数字

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

分数: 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

一个或多个方框可能是空的。