← 返回题目列表

AtCoder · arc151_d

D. 二进制表示和查询

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

分数: 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 按照此顺序,执行以下操作。

  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).
  2. 那么,如果 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