Xor Sum 3

题目描述

我们有 $N$ 个非负整数： $A_1, A_2, ..., A_N$ 。考虑将其中至少一个且至多 $N-1$ 个整数涂成红色，其余涂成蓝色。将画法的美丽值定义为被涂成红色的整数的 $\text{XOR}$ 与被涂成蓝色的整数的 $\text{XOR}$ 之和。求该画法可以达到的最大美丽值。

什么是 $\text{XOR}$？

$n$ 个非负整数 $x_1, x_2, \ldots, x_n$ 的按位异或 $x_1 \oplus x_2 \oplus \ldots \oplus x_n$ 定义如下：

当 $x_1 \oplus x_2 \oplus \ldots \oplus x_n$ 用二进制表示时，第 $2^k$ 位上的数字（ $k \geq 0$ ）为 $1$ 当且仅当在 $x_1, x_2, \ldots, x_n$ 中，其二进制表示在第 $2^k$ 位上为 $1$ 的整数的个数为奇数；若该计数为偶数，则该位为 $0$ 。

例如， $3 \oplus 5 = 6$ .

输入格式

输入按下列格式由标准输入给出： $N$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出能达到的最大美丽值。

3
3 6 5

4
23 36 66 65

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

2012721721873704572

提示

输入中的所有数值均为整数。 $2 \leq N \leq 10^5$ $0 \leq A_i < 2^{60}\ (1 \leq i \leq N)$ 如果我们将 $3$ , $6$ , $5$ 分别涂成蓝、红、蓝，则美丽值为 $(6) + (3 \oplus 5) = 12$ 。没有任何涂法能使美丽值超过 $12$ ，因此答案为 $12$ .
$A_i$ 和答案可能无法装入 32 位整数类型。

标签: AtCoder|abc141F

来源

AtCoder|abc141F

#2894. Xor Sum 3

Xor Sum 3

Xor Sum 3

题目描述

输入格式

输出格式

提示

来源

还没有账户？

登录