← 返回题目列表

AtCoder · arc137_d

D. 前缀异或

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

分数: 700 点

问题陈述

给你一个长度的整数序列 N: A=(A_1,A_2,\cdots,A_N),和一个整数 M.

对于每个 k=1,2,\cdots,M,找到值 A_N 执行以下操作后 k 次。

  • 对于每个 i (1 \leq i \leq N),同时替换 A_i 与 A_1 \oplus A_2 \oplus \cdots \oplus A_i.

在这里, \oplus 表示按位 \mathrm{XOR}.

什么是按位 \mathrm{XOR}?

按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B,定义如下:

  • 当 A \oplus B 以基数 2 书写,即 2^k的地点 (k \geq 0) 是 1 如果恰好是以下之一 A 和 B is 1,和 0 否则。
例如,我们有 3 \oplus 5 = 6 (以二为基数: 011 \oplus 101 = 110).
一般来说,按位 \mathrm{XOR} of k 整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)。我们可以证明这个值不依赖于顺序 p_1, p_2, p_3, \dots p_k.

约束

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 10^6
  • 0 \leq A_i < 2^{30}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \cdots A_N

输出

打印各个值的答案 k,用空格分隔。


示例输入 1

3 2
2 1 3

示例输出 1

0 1

每次操作都会改变 A 如下。

  • 最初: A=(2,1,3).
  • 第一次操作后: A=(2,3,0).
  • 第二次操作后: A=(2,1,1).

示例输入 2

10 12
721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427

示例输出 2

716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404