线性基总结模板

线性基

看了好多博客，，，，

线性基是一组数，是一个集合的产物，一般用来求原集合子集异或和极值的问题。

有什么作用？

通过线性基中元素xor出的数的值域与原来的数xor出数的值域相同。

但同时它这组数的大小只有原集合最大数的二进制位那麽多 (60 多位)，

线性基与原集合关于异或作用一样，但是他是最简的，好像线性代数里面叫做 基。

构造

求线性基时将一个数的二进制位看成一个向量。假定原集合为

数组，线性基为

对于每个

，按二进制从高位到低位扫，找最高位的 1，假如

的第

位是最高位的 1。

为 0 的话，即不存在，直接插入

；否则将

^=

，继续扫

其实相当于不断的将

const int base = 60;    // 一般long long 也就18位，即 60 多位二进制
int a[N], p[base+3];

for(int i = 0; i < n; i++){              // 对于每个数 a[i]
    for (int j = base; j >= 0; j--){     // 从高位到低位找 a[i] 最高位 1 的位置
        if(a[i] >> j & 1)             // 跳过前导 0
            if(!p[j]){                  // 该行没数，直接填
                p[j] = a[i];
                break;                  // 填完跳出
            }else{
                a[i] ^= p[j];           // 该行有数，异或之后继续看 a[i] 低位
            }
    }
}      

性质

1. 线性基中的每个向量的二进制最高位均不同，并且，我们称二进制最高位为第 i 位的元素称为“线性基的第 i 位”。
2. 原集合
3. 所在线性空间中每个元素都有唯一的方案由线性基中元素异或得到。

这样我们得到的

数组是一个上三角矩阵，而且元素全都是 0， 1。

类似于这样：

10010

01001

00100

00000

00001

可以知道线性基有多少组非零向量。

进一步简化

数组可以得到很多信息。下面两种方式将

for(int i = 0; i < n; i++){          // 对于每个数 a[i]
     for (int j = base; j >= 0; j--){ // 从高位到低位找 a[i] 的第一个不为 0 的数的位置
         if(a[i] >> j == 0)
             continue;               // 跳过前导 0
         if(!p[j]){                  // 该行没数，直接填
             p[j] = a[i];
             for (int k = j - 1; k >= 0; k--)    // 使第 p[j] 只有第 j 位为 1
                 if(p[k] && p[j]>>k&1)
                     p[j] ^= p[k];   // 下面的行消自己
             for (int k = j + 1; k <= base; k++)
                 if(p[k] >> j&1)
                     p[k] ^= p[j];   // 自己消上面的行
             break;
         }else{
             a[i] ^= p[j];           // 该行有数
         }
     }
 }      

for(int i = base; i >= 0; i--){
     if(!p[i])
         continue;
     for (int j = i + 1; j < base; j++){
         if(p[j]>>i&1)
             p[j] ^= p[i];
     }
 }      

得到对角矩阵之后可以算第

// 求线性基时加上
for (int i = 0; i <= base; i++){    // 后面查询用到，存非零位
    if(p[i]){
        v.push_back(p[i]);
    }
}

ll ask(ll x){               // 查询第 k 小
    if(v.size() != n)       // 线性有关，可以异或出来 0
        x--;
    if(!x)
        return 0;           // 第一小的数是 0
    if(x >= (1LL << v.size()))  // x 超出所有能得到的值数量的范围
        return -1;
    // 能得到 0，x 已经 -1了，x 最多达到2^v.size()-1;
    // 不等得到 0，x 最多达到v.size()-1
    ll ans = 0;
    for(int i = 0; i <= base; i++){ // 将第 i 为异或起来
        if(x >> i&1){           // 第 i 位为 1
            ans ^= v[i];
        }
    }
    return ans;
}      

参考

​​​​https://blog.sengxian.com/algorithms/linear-basis​​