分数: 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 否则。
约束
- 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