重修 线性基

Luogu 例题

Someone's Blog

概念

（自己总结的）

大小 \(\log n\) 的数组来表述一个大小为 \(n\) 的原数组的异或问题的数据结构。

本质

多维向量的作为基底的特殊形式，可用高斯消元理解。

构造

本构造线性基中每一个数 \(x\) 都对应了原来每一个二进制位，即 \(upperbit(x)\)，所以线性基的二进制最高位互不相同。

我们构造 \(\{a\}\) 的线性基 \(\{p\}\)。

每次插入一个数 \(x\in\{a\}\)，如果 \(\exists y\in\{p\}\ |\ upperbit(x)=upperbit(y)\)（即若 \(y\) 想加入线性基，她所属的二进制位已被占），则 \(x'=x\operatorname{xor} y\)，这使得 \(upperbit(x')，递推即可。当然若 \(x\) 最后为 \(0\) 则他与前面的线性基线性有关，废掉 \(x\)。

void insert(int x){
    for(int i = 63;i>=0;i--){
        if(x&(1ll<

for(long long i=62;i>=0;i--)
    if((p[i]^ans)>ans)
        ans^=p[i];