← 返回题目列表

AtCoder · arc173_e

E. 重新排列和相邻异或

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

分数: 800 点

问题陈述

给你一系列 N 非负整数 A=(A_1,A_2,\dots,A_N)。考虑执行以下操作 N-1 次此序列以获得长度的序列 1:

  • 让 n 的长度 A。首先,重新排列元素 A 按照您喜欢的任何顺序。 然后,更换 A 具有一系列 n-1 非负整数 (A_1 \oplus A_2, A_2 \oplus A_3, \dots, A_{n-1} \oplus A_n).

在这里, \oplus 表示按位 \mathrm{XOR} 操作。

让 X 是长度序列中包含的项的值 1 之后获得 N-1 操作。找出最大可能值 X.

什么是按位 \mathrm{XOR} 操作?

按位 \mathrm{XOR} 两个非负整数 A 和 B,表示为 A \oplus B,定义如下:

  • 在二进制表示中 A \oplus B,位于的数字 2^k (k \geq 0) 位置是 1 如果数字位于 2^k 位置是 1 in A or B 但不是两者,并且 0 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \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.

约束

  • 2 \leq N \leq 100
  • 0 \leq A_i < 2^{60}
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \dots A_N

输出

打印答案。


样本输入 1

4
1 2 3 4

示例输出 1

7

序列 A 可以转化为 A=(7) 通过以下三个操作:

  • 在第一次操作中,重新排列 A=(1,2,3,4) to (3,1,4,2). A 替换为 (3 \oplus 1, 1 \oplus 4, 4 \oplus 2) = (2,5,6).
  • 在第二次操作中,重新排列 A=(2,5,6) to (2,6,5). A 替换为 (2 \oplus 6, 6 \oplus 5) = (4,3).
  • 在第三次操作中,重新排列 A=(4,3) to (4,3). A 替换为 (4 \oplus 3) = (7).

示例输入 2

13
451745518671773958 43800508384422957 153019271028231120 577708532586013562 133532134450358663 619750463276496276 615201966367277237 943395749975730789 813856754125382728 705285621476908966 912241698686715427 951219919930656543 124032597374298654

示例输出 2

1152905479775702586