#abc141f. [abc141_f]Xor Sum 3

[abc141_f]Xor Sum 3

题目描述

我们有 NN 个非负整数:A1,A2,...,ANA_1, A_2, ..., A_N

考虑将其中至少一个、最多 N1N-1 个整数涂成红色,其余的涂成蓝色。

定义绘画的“美观度”为红色区域中整数的异或和加上蓝色区域中整数的异或和。

找到绘画的最大可能美观度。

什么是异或(XOR)?

对于 nn 个非负整数 x1,x2,...,xnx_1, x_2, ..., x_n,异或运算 x1x2xnx_1 \oplus x_2 \oplus \ldots \oplus x_n 的定义如下:

  • 当将 x1x2xnx_1 \oplus x_2 \oplus \ldots \oplus x_n 转化为二进制时,在第 2k2^k 位(k0k \geq 0)的数字为 11,当且仅当 x1,x2,...,xnx_1, x_2, ..., x_n 中具有该位为 2k2^k 的二进制表示中的 11 的整数数量是奇数时,该位为 11;否则,该位为 00

例如,35=63 \oplus 5 = 6

约束条件

  • 输入数据中的所有值都是整数。
  • 2N1052 \leq N \leq 10^5
  • 0Ai<260 (1iN)0 \leq A_i < 2^{60}\ (1 \leq i \leq N)

输入格式

从标准输入读入输入数据,输入格式如下:

NN A1A_1 A2A_2 ...... ANA_N

输出格式

输出绘画的最大可能美观度。

示例输入1

3
3 6 5

示例输出1

12

如果我们将整数 336655 涂成蓝色、红色、蓝色,那么美观度将是 (6)+(35)=12(6) + (3 \oplus 5) = 12

没有比 1212 更高美观度的涂法,因此答案是 1212

示例输入2

4
23 36 66 65

示例输出2

188

示例输入3

20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181

示例输出3

2012721721873704572

AiA_i 和答案可能无法适应 3232 位整数类型。