← 返回题目列表

AtCoder · cpsco2019_s3_e

E. 枚举异或和

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

配点 : 500 点

問題文

长度 N 的 0 的整数序列 给出了 A_1, A_2, \ldots, A_N 。每个 对于 k = 1, 2, \ldots, N 作为

  • X = A_1 {\rm xor} A_2 {\rm xor} \ldots {\rm xor} A_k , 输出
  • (A_1 {\rm xor} X) + (A_2 {\rm xor} X) + \ldots + (A_k {\rm xor} X) 的值 请创建一个类似

的程序。X 的定义是 请注意,它会根据 k 而变化。

另外,一个整数 c_1, c_2, \ldots, c_m 的 {\rm xor} 定义如下:

  • 寻求 {\rm xor} 的值 X 当
  • X 表示为二进制数时, 2^k (k 满足 0 或更大的位值是c_1, c_2, \ldots, c_m 当表示为二进制数时 2^k 的位值为 如果有奇数个 1 如果有奇数个 1,如果有偶数 0 变为。

制約

  • 1 \le N \le 3 \times 10^5
  • 0 \le A_i < 2^{30}
  • 提供的所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。 逐行打印

N
A_1 A_2 \ldots A_N

出力

各 k = 1, 2, \ldots, N 的答案。


入力例 1

3
7 5 3

出力例 1

0
12
12
  • k = 1 时, 当您移动到X = 7 所以, 从A_1 {\rm xor} X = 0 。
  • k = 2 时, 当您移动到X = 7 {\rm xor} 5 = 2 所以, 从A_1 {\rm xor} X = 5、A_{2} {\rm xor} X = 7 开始,总值为 12 。
  • k = 3 时, 当您移动到X = 7 {\rm xor} 5 {\rm xor} 3 = 1 所以, 从A_1 {\rm xor} X = 6、A_{2} {\rm xor} X = 4、A_{3} {\rm xor} X = 2 开始,总值为 12 。

入力例 2

7
12 42 61 31 34 53 17

出力例 2

0
54
110
138
142
233
252