题解

思路

任意两项的异或值在操作前后保持不变；而只要至少进行一次操作，最后一次选中的元素会变成 $0$。

做法

因此所有可达序列恰好是原序列，以及对某个原始元素 $A_k$ 将全体异或 $A_k$ 得到的序列。于是只需枚举 $x\in\{0,A_1,\ldots,A_N\}$，计算 $\sum_i(A_i\oplus x)$ 的最大值。

对每个二进制位预处理原序列中该位为 $1$ 的元素个数。若 $x$ 在这一位为 $0$，贡献为原有的 $1$ 的数量；若为 $1$，贡献则来自原有的 $0$。

复杂度

这样每个候选只需检查 30 位，总时间复杂度为 $O(30N)$，空间复杂度为 $O(N)$。