异或线性基
模板题：【模板】线性基
一个数列 \(a\) 的异或线性基 \(p\) 满足：\(a\) 的任意子集的异或和 \(sum\)，必然能在 \(p\) 中找到一个子集，其异或和也为 \(sum\)。
思路
先考虑构造 \(a=\{x,y\}\) 的异或线性基。
构造 \(p=\{x,x\oplus y\}\)。
\(a\) 的子集异或和与 \(p\) 的子集异或和对应：
-
\(a'=\{x\},p'=\{x\},sum=x\)
-
\(a'=\{y\},p'=\{x,x\oplus y\},sum=y\)
-
\(a'=\{x,y\},p'={x\oplus y},sum=x\oplus y\)
这是组成异或线性基的基本单位，整体异或线性基的构造思路与之基本相同。
异或线性基的构造方式为增量法，令当前异或线性基为 \(p\)，（\(p_i\) 表示异或线性基中二进制最高位为 \(i\) 的数），新加入的数为 \(x\)，流程如下：
-
令 \(x\) 最高位为 \(b\)，分类讨论：
-
若 \(p\) 中没有最高位为 \(b\) 的数，直接将 \(x\) 加入即可。（\(p_b\gets x\)）
-
否则，将 \(x\) 异或上 \(p_b\)，将 \(b\) 更新为 \(x\) 现在的最高位，再次分类讨论（\(x\gets x\oplus p_b\)）
-
这样，异或线性基内二进制下长度相同的的数只会有一个，其大小为 \(O(v)\) 级别。
现在考虑查询子集异或最大值，根据异或线性基的定义。
\(i\) 从大到小枚举 \(p_i\)，有性质：若加入 \(p_i\) 能使答案变大，选它一定更优。（后面的最高位比 \(i\) 小）
直接不断更新 \(ans=\max(ans,ans\oplus p_i)\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;
long long n, p[55];
inline void insert(long long x) {
for (int i = 51; i >= 0; i--) {
if (!(x >> i & 1))
continue;
if (!p[i]) {
p[i] = x;
break;
}
x ^= p[i];
}
}
inline long long query() {
long long ret = 0;
for (int i = 51; i >= 0; i--)
ret = max(ret, ret ^ p[i]);
return ret;
}
int main() {
cin >> n;
while (n--) {
long long x;
cin >> x;
insert(x);
}
cout << query();
return 0;
}