最优异或值

题目描述

给定 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$ ，你需要确定一个非负整数 $x$ ，使得 $a_1 \oplus a_2 \oplus \cdots \oplus a_n \oplus x$ 的值最小。

你需要输出这个 $x$ 以及对应的最小值。

其中 $\oplus$ 代表按位异或运算，即 C++ 中的 ^ 运算符。对于两个非负整数的每一位：

例如： $0 \oplus 0 = 0$ ， $1 \oplus 0 = 1$ ， $0 \oplus 1 = 1$ ， $1 \oplus 1 = 0$ 。

输入共两行。

第一行一个整数 $n$ ，表示序列长度。
第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$ 。

输出一行两个整数： $x$ 和 $a_1 \oplus a_2 \oplus \cdots \oplus a_n \oplus x$ 。

2
1 2

3 0

2
7 7

0 0

对于 $100\%$ 的数据， $1 \leq n \leq 10 ^ 6$ ， $0 \leq a_i \leq 10 ^ {18}$ 。

测试点	$n$	$a_i$	特殊性质
$1$	$= 1$	$\leq 10 ^ 3$	无
$2$	$= 2$	$\leq 10 ^ 3$	$a_1 = a_2$
$3 \sim 4$	$= 2$	$\leq 10 ^ 3$	无
$5$	$\leq 10 ^ 3$	$= 0$	无
$6 \sim 8$	$\leq 10 ^ 3$	$\leq 10 ^ 3$	无
$9 \sim 11$	$\leq 10 ^ 6$	$\leq 10 ^ 3$	无
$12 \sim 13$	$\leq 10 ^ 6$	$\leq 1$	无
$14 \sim 20$	$\leq 10 ^ 6$	$\leq 10 ^ {18}$	无

难度入门

通过率 —

尝试 0

已通过 0

标签