题解 P3812 【【模板】线性基】
rui_er
2020-10-12 17:54:46
刚刚口胡并学了线性基，就来写篇题解，记录一下。
---
从 $n$ 个数中选取若干个，使他们的异或和最大。
既然是异或和，因为异或是位运算，肯定要用到二进制的。
考虑异或和的性质：对于这一位，有奇数个 $1$ 求异或和，结果为 $1$；有偶数个 $1$ 求异或和，结果为 $0$。这一性质告诉我们，当我们对当前位置完成决策的时候，后面所有位的异或和无论怎样也不会影响到现有结果。想到从高位到低位扫一遍，对每一位取最优决策，就是结果。
但因为每一位二进制位可能有很多 $1$，不方便进行决策，于是思考能不能**构造一个序列，使得在这个序列中，任取若干个数求异或和的结果组成的集合，与原序列求异或和的结果组成的集合一样，且这个序列的每个数的最高位 $1$ 所在位数不一样**呢？这种情况下，我们在新序列上决策和在原数列上决策是等效的。
~~但是我太菜了发现并不会构造，怎么办呢？上百度搜线性基正解吧。~~
结果一搜发现我已经口胡出来了，愣是傻傻的不会构造 /jk /jk，那就继续说吧。
线性基就是由原数列集合构造出的满足下面性质的集合：
1. 线性基内的元素可以通过求异或和，得到原集合的元素任意求异或和得到的所有值。
2. 线性基是满足上面性质的最小的集合。
3. 线性基不存在异或和为 $0$ 的子集。
4. 线性基中，任取不同的子集求异或和，得到的答案不同。（即线性基子集的异或和具有唯一性）
5. 线性基内所有元素的二进制最高位互不相同。
考虑进行构造：
在线性基插入元素 $x$，从高位向低位扫，如果 $x$ 二进制下该位为 $1$，且不存在最高位为该位的线性基元素，将其加入线性基。如果该位为 $1$，但已经存在元素的最高位为该位，将 $x$ 异或上该元素，继续向后搜。
要查询最大值，从高位到低位枚举线性基中最高位为该位的元素，如果答案异或上这个数比原来的答案大，更新答案。这样因为更低位的结果无法影响当前位，因此这一方法是最优的。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 55, bit = 50;
ll n, a, p[N];
void insert(ll k) {
for(ll i=bit;i>=0;i--) {
if(!(k&(1LL<<i))) continue;
if(!p[i]) return p[i] = k, void();
k ^= p[i];
}
}
ll maxXor() {
ll res = 0;
for(ll i=bit;i>=0;i--) res = max(res, (res^p[i]));
return res;
}
int main() {
scanf("%lld", &n);
while(n--) {scanf("%lld", &a); insert(a);}
printf("%lld\n", maxXor());
return 0;
}
```