学习心得 - 数学 - 线性基

ExFish · 2025-03-26 18:00:11 · 算法·理论

突然不知道为什么要学线性基。

用处

• 求一个数能不能被 \{a_i\} 异或出来。
• 求 \{a_i\} 能异或出来的第 k 大值，\max 和 \min。

我们设置这个线性基为 \{l_i\}，那么有：

• 原序列 \{a_i\} 可以通过 \{l_i\} 异或出来。
• 这个线性基不唯一，但是数的数量最少。

插入线性基

从高到低位，要是 x_i=1，且 p_i=0，那么插入一个 p_i=x。

否则 p_i=1，x=x\otimes p_i。

为什么这是线性基呢？

证明：

1. 当没有插入 x_i，那么会不存在，或 x_i\otimes p_i=0，说明 \{l_i\} 的数可以异或出 x。符合性质 3。
2. 注意到要是 \otimes_{j\in \{l_i\}}=0，那么一定存在一个 l_i 可以被表示出来，就不会被插入了。符合性质 4。

具体代码：

void insert(ll val){
    for(int i=60;i>=0;i--)if(val&(1ll<<i)){
        if(!l[i]){
            l[i]=val,++sz;
            break;
        }else val^=l[i];
    }
}

查询是否可以被异或

按照上述性质写写即可。

不贴代码了。

查询异或最大值

直接贪心。

代码：

ll getmax(){
    ll val=0;
    for(int i=60;i>=0;i--)if((val^(1ll<<i))>val)
        val^=l[i];
    return val;
}

查询异或最小值

注意到线性基没有 0，但是答案可以为 0，特判即可。

不贴代码。