题解 | #汉堡猫猫#

讲一个和官方题解不太一样的做法。

一开始套路地想到从高位到低位贪心，即尽可能让高位为 $1$ ，如果能使得某一位为 $1$ ，在确保这一位为 $1$ 的情况下继续向低位贪心。但这是不太好做的，因为在处理低位时，很难保证高位为 $1$ 。

观察样例发现，如果序列中恰有奇数个奇数，那么答案为 $2^{61} - 1$ ，也就是可以让答案的所有位都是 $1$ 。因为我们可以让奇数都变成 $2^{61} - 1$ ，偶数都变成 $0$ ，这样异或和就是 $2^{61} - 1$ 。

如果奇数的个数是偶数呢？由于最低位不能被修改，所以答案的最低位只能是 $0$ 。那么我们可以把所有数的最低位删掉，递归处理下一位。一般地，如果对于所有 $0 \le j < i$ ，序列中恰有偶数个元素的第 $j$ 位是 $1$ ，而有奇数个元素的第 $i$ 位是 $1$ ，那么答案的第 $0 \sim i - 1$ 位只能是 $0$ ，而我们可以把那些第 $i$ 位是 $1$ 的元素操作成

111...1c_{i - 1}\dots c_{1}c_{0}

其它元素操作成

000...0c_{i - 1}\dots c_{1}c_{0}

于是答案的第 $0 \sim i - 1$ 位是 $0$ ，而 $i \sim 60$ 位是 $1$ 。

还需要考虑一种情况：序列中第 $i$ 为是 $1$ 的元素数量为偶数，但可以调整为奇数。这需要存在某个元素的第 $(i - 1)$ 位和第 $i$ 位不同。

最后特判一下序列全是 $0$ 的情况即可。

代码