← 返回题目列表

AtCoder · arc135_c

C. 全部异或

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

分数: 500 点

问题陈述

给你一个非负整数序列 A = (A_1, \ldots, A_N)。 您可以执行以下操作任意次数(可能为零)。

  • 选择一个整数 x\in \{A_1,\ldots,A_N\}.
  • 替换 A_i 与 A_i\oplus x 对于每个 i (\oplus 表示按位 \mathrm{XOR} 操作)。

找到最大可能值 \sum_{i=1}^N A_i 操作后。

什么是按位 \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).

约束

  • 1\leq N \leq 3\times 10^{5}
  • 0\leq A_i < 2^{30}

输入

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

N
A_1 \ldots A_N

输出

打印最大可能值 \sum_{i=1}^N A_i 操作后。


示例输入 1

5
1 2 3 4 5

示例输出 1

19

这是实现的操作序列 \sum_{i=1}^N A_i = 19.

  • 最初,序列 A is (1,2,3,4,5).
  • 操作 x = 1 将其更改为 (0,3,2,5,4).
  • 操作 x = 5 将其更改为 (5,6,7,0,1),其中 \sum_{i=1}^N A_i = 5 + 6 + 7 + 0 + 1 = 19.

示例输入 2

5
10 10 10 10 10

示例输出 2

50

进行零运算实现 \sum_{i=1}^N A_i = 50.


示例输入 3

5
3 1 4 1 5

示例输出 3

18