XorAndSum
作者：赵晟宇 陈俊锟
关键词：线性基 高斯消元 异或
题目简述
给定一个长度为的整数序列。每次操作选择两个整数，将修改为与的二进制异或，而不变。不限操作次数，求序列中所有数之和的最大值。
算法
若我们求出一组异或线性基（线性基的定义这里就不重述了），那么线性基内部可以构造出一个最大值，线性基外的每个数亦可在归之后同样变成这个最大值。所以我们首先用高斯消元求出序列的异或线性基，并保证每列（每个二进制位）最多包含一个。这时把所有的数异或起来即可得到最大值，因为只有那些没有的列异或之后的结果是，而这些列无论怎样操作也不可能出现。我们选择最高位为的数，把它与其它的每个数异或，操作成最大值。然后，将其它的每个数与这个最大值异或，可以证明这样得到的序列即为最优序列。
我们下面来证明这个算法的正确性。
容易发现，题目中的操作是可逆的。即，无论如何都可以再通过若干次操作使其恢复初始状态（倒序执行操作序列即可）。
对于线性基中除最高位外存在的每一列，答案序列在该列上有且仅有一个。现在用反证法来说明，对于线性基中除最高位外存在的第列，均至少有一个。若第列上没有，即全是，则答案序列中的每个数的最高位与第位都是相同的。不论再经过多少次操作，显然序列中每个数的最高位与第位仍都是相同的。而由于操作是可逆的，与线性基中的解矛盾，这样的答案序列无法恢复成初始序列。
算法得证。
时间复杂度，空间复杂度。
算法的另一种描述
上面这个算法描述有一些问题，在这里重新整理一下。
考虑构造出最优解，从高位到低位高斯消元，代码如下：
long long G[64] = {};
for(int _ = 0; _ != n; ++_)
for(long long x = val[_]; x; )
{
int k = 63 - __builtin_clzll(x);
if(!G[k]) {G[k] = x; break;}
x ^= G[k];
}
通过上述代码执行后，我们可以得到 G 数组，这个数组中的非 0 位构成了原集合的线性基。如果 G[i] == 0，则说明 与 的更高位线性相关（即第 位是否为 1 完全取决于高于 的那些位置是否为 1）；否则，说明 与 的更高位线性无关，我们称 G[i] 是第 位的线性基。为了方便，我们对线性基进行处理，使得如果第 位和更高位线性无关，那么在这些基中，只有 G[i] 的第 位为 1。这个步骤类似高斯消元解方程的回代，代码如下：
for(int i = 0; i != 64; ++i) if(G[i])
for(int j = i + 1; j != 64; ++j) if(G[j] & (1ll << i)) G[j] ^= G[i];
这样处理之后，我们把所有非 0 的 G[i] 异或起来，得到的数就是最大异或子集。证明：从高位到低位考虑每一位能否是 ，首先如果第 位和更高的位线性相关，则第 位已经确定，无法修改；否则，由于我们保证了只有 G[i] 的第 位是 ，因此第 位是否为 就只和 G[i] 是否被选有关，我们一定会将其选择，这样每一位都是在更高位确定的基础上尽可能的大。
设有 个二进制位和更高位线性无关，则在高斯消元后有 个数为 0，我们可以把它们都变成最大异或子集，剩下需要考虑的就是那些 G 中的元素了。正确的策略是这样的：首先，把出现的最高位（设为第 位，显然它和更高位线性无关）的基异或上其他的基，变成最大异或子集，然后将其他的每一个 G[i]（) 和其他所有为 0 的数异或上最大异或子集，这样构造出的集合的和是最大的。
考虑证明。首先是合法性，高斯消元的方式是将一行异或上另一行，后面的构造也是这样的形式，均符合题目要求。然后对于那些不为 并且和更高位线性无关的二进制位 ，如果最终的集合中每一个数的第 位都是 1，那么又因为（由构造方式）最终的集合中每个数的第 位都是 1，则说明第 位和第 位线性相关（具体地说，任一异或子集中第 位和第 位均相等），和“第 位和更高位线性无关”矛盾，因此第 位一定至少存在一个位置不是 。
在上述的算法中，对于每一个 ，我们都是将 G[i] 变为其他几位的基的异或和，这个数正是“强制要求第 位为 0 的最大异或子集”。因此我们的算法中，每一位都取到了能取的最大值，算法的正确性得证。
沿用上文中最高位 的定义，则时间复杂度为 ，空间复杂度为 。