分数: 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 否则。
一般来说,按位 \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