线性基的定义
在一个高维空间中一组极大的线性无关的向量组成为一组线性基,更严谨的定义参考线性代数相关内容。
但是在 OI 中我们常用的是异或线性基,它维护了给定若干个数能够通过异或计算出的所有的数,具体来说可以实现以下几个功能:
- 求 min/max 异或和
- 求 k 大异或和
- 求异或和数量
线性基的构建
分为高斯消元法和贪心法,这里介绍贪心法。
考虑插入一个数 \(x\),从高位到低位遍历一个线性基,如果当前位线性基内没有值,那么把 \(x\) 作为当前位的代表值,否则让 \(x\) 异或上这一位,继续插入。
考虑这样做的正确性,从低位到高位插入,如果当前位没有值,那么 \(x\) 必不可能被表示,反之则 \(x\) 的这一位可有可无,如果一直到最后 \(x\) 都没有被插入,则我们认为本次插入失败。
需要注意的是,我们构建出来的只是一个能实现线性基功能的东西而不是严格的线性基,
code:
bool insert(int x){
for(int i = 60; i >= 0; --i){
if(!(x & (1ll << i))) continue;
if(p[i]) x ^= p[i];
else {p[i] = x; return 1;}
}
return 0;
}
求最大/最小异或和
继续考虑贪心,我们从高位到