Readme

3681.Maximum-XOR-of-Subsequences

这是一道“异或空间线性基”的模版题。

首先定义“异或空间线性基”。对于一组数字集合nums，任意选取若干进行异或操作所能构成的结果记作空间S。如果另一组数字Basis同样也能构成S，并且Basis所需的数字最少，那么Basis就成为原数字集合的一组“异或空间线性基”。举个例子，比如nums={9,11,12,14}，它所能构成的异或空间S={2,5,7,9,11,12,14}. 通过某种算法，我们可以找到一组线性基B={12,5,2}，并且可以验证B能构造的异或空间也是S。另外，我们所构造的线性基有一个特点，每个元素的leading one的位置都不相同。比如{12,5,2}，其二进制表达就是{1100,0101,0010}，可以观察到最高位的位置依次降低。

假设我们能找到nums的一组线性基B，那么nums能组成的最大异或值，等价于其线性基B能组成的最大异或值。而对于B，由于有前述的性质（最高位的位置依次降低），我们可以用贪心法来从大到小进行选择：第i个元素的选择取决于答案的第i个bit位是否会退化。

int ret = 0;
for (int b: basis) {
  ret = max(ret, ret^b);
}

接下来我们学习如何构造这样的异或空间线性基。举个例子：a=2, b=5, c=11, d=6

   3 2 1 0
a  0 0 1 0
b  0 1 0 1
c  1 0 1 1
d  0 1 1 0

首先考察a=0010，最高位在第1位，且我们还没有最高位在第1位的基存在，所以我们可以确定一个最高位在第1位的基：b(1) = 0010.

接着考察b=0101，最高位在第2位，且我们还没有最高位在第2位的基存在，所以我们可以确定一个最高位在第2位的基：b(2) = 0101.

然后考察c=1011，最高位在第3位，且我们还没有最高位在第3位的基存在，所以我们可以确定一个最高位在第3位的基：b(3) = 1011.

最后考察d=0110，最高位在第2位，我们已经确定了b(2)，所以我们与b(2)结合d^b(2) = 0110^0101 = 0011。它的最高位在第1位，而我们已经确定了b(1)，我们就再与b(1)结合0011^0010=0001，此时它的最高位在第0位，且我们还没有最高位在第0位的基存在，所以我们可以确定一个最高位在第0位的基：b(3) = 0001.

综上，我们得到了一组线性基b(3)=11, b(2)=5, b(1)=2, b(0)=1.

以上的算法总结成代码模板就是：

vector<int>basis(32, 0);
for (int x: nums) {
    for (int i=31; i>=0; i--) {
        if (!(x>>i)&1) continue;
        if (!basis[i]) {
            basis[i] = x;
            break;
        }
        x ^= basis[i];
    }
}