← 返回题目列表

Codeforces · 1322/B

B. 礼物

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

凯瑟琳在 3 月 8 日收到了一组整数作为礼物。最终她对此感到厌倦,并开始为其计算各种无用的特征。她成功地完成了她想出的每一件作品。但是,当她想出另一个方法时——对数组中所有成对的元素进行异或,她意识到自己无法计算一个非常大的数组,因此她请求您的帮助。你能做到吗?正式地,您需要计算

$$$$$$ (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ $$$$$$

这里 $$$x \oplus y$$$ 是按位异或运算(即许多现代编程语言中的 $$$x$$$ ^ $$$y$$$)。您可以在维基百科中阅读相关内容:https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 400\,000$$$) — 数组中整数的数量。

第二行包含整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$)。

输出

打印单个整数 - 给定数组中所有成对整数和的异或。

示例

输入 #1

2
1 2

输出 #1

3

输入 #2

3
1 2 3

输出 #2

2

注意

在第一个示例中,只有一个总和 $$$1 + 2 = 3$$$。

在第二个示例案例中,有三个总和:$$$1 + 2 = 3$$$、$$$1 + 3 = 4$$$、$$$2 + 3 = 5$$$。在二进制中,它们表示为 $$$011_2 \oplus 100_2 \oplus 101_2 = 010_2$$$,因此答案是 2。

$$$\oplus$$$ 是按位异或运算。要定义 $$$x \oplus y$$$,请考虑整数 $$$x$$$ 和 $$$y$$$ 的二进制表示形式。当 $$$x$$$ 和 $$$y$$$ 的第 $$$i$$$ 位中恰好有一个为 1 时,我们将结果的第 $$$i$$$ 位设置为 1。否则,将结果的第 $$$i$$$ 位设置为 0。例如,$$$0101_2 \, \oplus \, 0011_2 = 0110_2$$$。