算法竞赛笔记.异或线性基

数集的线性基是另一个数集，每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原数集中的任何一个数。

线性基有如下性质：

• 原数集的任意一个数都可以由线性基内部的一些数异或得到。
• 线性基内部的任意数异或起来都不能得到 $0$。
• 线性基内部的数个数唯一；且在保持性质一的前提下，数的个数是最少的。

基本操作

插入

bool insert(int x){ // 插入一个新数 x
    for(int i=60;i>=0;i--){//从 x 高位到低位
        if(x>>i&1) {
            if(!p[i]){// 如果阶梯形的这一位还没有基底
                p[i]=x;return true;// x是新的基底
            }else{
                x^=p[i];// 消除这一位
            }
        }
    }
    return false;// x和已有元素线性相关，不需要插入
}

求最大值

如 洛谷 P3812 【模板】线性基 ，给定 $n$ 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

先构造出线性基，再从高到低位贪心即可。

求最小值

求原数集能异或出的最小值。

如果原数集中有不能插入线性基的数（线性相关），则答案为 $0$ 。否则答案为线性基中最小的元素。

求 $k$ 小值

从一个数集中取任意元素进行异或，求能异或出的所有数字中第 $k$ 小的那个。

先预处理线性基：对每一个 $p_i$，枚举 $j=i-1 \rightarrow 0$，如果 $p_i$ 二进制第 $j$ 位为 1，则异或上 $p_j$。

对于 $k$ ，将 $k$ 先转成二进制，假如第 $i$ 位为 $1$，则将答案异或线性基中第 $i$ 个元素。