分数: 700 点
问题陈述
给你一个整数序列 A = (A_0, A_1, \ldots, A_{2^N-1}) 长度 2^N.
此外, 给出了 Q 查询。 对于每个 i = 1, 2, \ldots, Q, i-第一个查询由两个整数表示 X_i 和 Y_i 并要求您执行以下操作。
对于每个 j = 0, 1, 2, \ldots, 2^N-1 按照此顺序,执行以下操作。
- 首先,让 b_{N-1}b_{N-2}\ldots b_0 是以下的二进制表示 j 与 N 数字。另外,让 j' 是二进制表示的整数 b_{N-1}b_{N-2}\ldots b_0 翻转位后 b_{X_i} (改变 0 to 1 和 1 to 0).
- 那么,如果 b_{X_i} = Y_i,添加值 A_j to A_{j'}.
打印每个元素 A,模数 998244353,按照输入中给出的顺序处理所有查询后。
什么是二进制表示 N 数字?
非负整数的二进制表示 X (0 \leq X < 2^N) 与 N 数字是唯一的序列 b_{N-1}b_{N-2}\ldots b_0 长度 N 组成 0 和 1 满足:
- \sum_{i = 0}^{N-1} b_i \cdot 2^i = X.
约束
- 1 \leq N \leq 18
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq A_i \lt 998244353
- 0 \leq X_i \leq N-1
- Y_i \in \lbrace 0, 1\rbrace
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q
A_0 A_1 \ldots A_{2^N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
输出
对于每个 i = 0, 1, \ldots, 2^N-1,打印余数 A'_i 分割时 A_i 处理所有查询后 998244353,以空格分隔,格式如下:
A'_0 A'_1 \ldots A'_{2^N-1}
示例输入 1
2 2 0 1 2 3 1 1 0 0
示例输出 1
2 6 2 5
第一个查询要求您执行以下操作。
- 对于 j = 0,我们有 b_1b_0 = 00 和 j' = 2。自从 b_1 \neq 1,跳过加法。
- 对于 j = 1,我们有 b_1b_0 = 01 和 j' = 3。自从 b_1 \neq 1,跳过加法。
- 对于 j = 2,我们有 b_1b_0 = 10 和 j' = 0。自从 b_1 = 1,添加值 A_2 to A_0。现在我们有 A = (2, 1, 2, 3).
- 对于 j = 3,我们有 b_1b_0 = 11 和 j' = 1。自从 b_1 = 1,添加值 A_3 to A_1。现在我们有 A = (2, 4, 2, 3).
第二个查询要求您执行以下操作。
- 对于 j = 0,我们有 b_1b_0 = 00 和 j' = 1。自从 b_0 = 0,添加值 A_0 to A_1。现在我们有 A = (2, 6, 2, 3).
- 对于 j = 1,我们有 b_1b_0 = 01 和 j' = 0。自从 b_0 \neq 0,跳过加法。
- 对于 j = 2,我们有 b_1b_0 = 10 和 j' = 3。自从 b_0 = 0,添加值 A_2 to A_3。现在我们有 A = (2, 6, 2, 5).
- 对于 j = 3,我们有 b_1b_0 = 11 和 j' = 2。自从 b_0 \neq 0,跳过加法。
因此, A 将是 (2, 6, 2, 5) 处理完所有查询后。
示例输入 2
3 10 606248357 338306877 919152167 981537317 808873985 845549408 680941783 921035119 1 1 0 0 0 0 0 0 0 1 0 1 0 1 2 0 2 0 2 0
示例输出 2
246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980