（二进制)线性基

· · 个人记录

觉得二进制线性基又是一个数据结构，因此就单独搬出来了。

详见：线性基详解

线性基的构造

d[i]存着一个线性基，它的最高位为第i位。（d[i]可能为空）

inline void ins(ll num) {
    for (register int i = 52; ~i; --i)
        if ((num >> i) & 1) {
            if (!d[i])  return d[i] = num, void();
            num ^= d[i];
        }
}

找最大异或和

即这道例题：P3812 【模板】线性基

贪心：由于线性基就是一些数异或得到的，因此设答案res，从高位到低位扫线性基数组，如果能使res更大，就让res更大。

ll res = 0;
for (register int i = 52; ~i; --i) 
    if ((res ^ d[i]) > res)
        res ^= d[i];

但是有时要开好多线性基，连35的数组都开不下，这时就需要用vector了。

注意到每次能把 x 加入线性基，当且仅当 x 不能被d[] 中的数线性表出（无法被异或成0）。因此我们每次贪心异或（尽可能往小里异或），如果最后非0就加入，同时维护有序性。

查最大就像往常一样，从大到小贪心即可。

struct line{//线性基 
    vector<int> d;
    inline void add(int x) {
        for (register int i = 0; i < d.size(); ++i) 
            if ((x ^ d[i]) < x) x ^= d[i];
        if (!x) return ;
        d.push_back(x);
        for (register int i = d.size() - 1; i; --i) {//slow sort
            if (d[i] > d[i - 1])    swap(d[i], d[i - 1]);
        }
    }
    inline int get_max() {
        int res = 0;
        for (register int i = 0; i < d.size(); ++i)
            if ((res ^ d[i]) > res) res ^= d[i];
        return res;
    }
};

注意！！！

记得判(num >> i) & 1 ！！！

第二种线性基写法不能改成d数组递增的形式，我也不知道为什么。

这样插的线性基符合三条性质：

线性基三大性质
1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到
2.线性基里面的任意一些数异或起来都不能得到0
3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
- by ryc学长课件，上面博客也有写到

线性基的应用

找最小异或和

贪心：如果之前插入时失败过，就为0，否则最小异或和就是最小的d[i]。

找第k小异或和

首先把所有的d都搞成"1xx0xxxx0xxx0xx"的样子（0表示那一位可以被异或成为0）（此时d仍然为线性基）。

然后把k拆成二进制，并从小到大扫d数组。如果d[i]非0（那一位可以自由选择），就根据k的最后一位情况决定是否异或上d[i]。

因为d[i]代表第i位是否为1，那么只要我们把d[i]是否异或和k的二进制对应起来，答案就是正确的。

注意判断一下异或和为0是第一小的情况。

代码大概长这样：

for (register int i = 52; ~i; --i){if (d[i])
    for (register int j = i - 1; ~j; --j)
        if (d[j] && d[i] & (1ll << j))
            d[i] ^= d[j];
ll res = 0;
for (register int i = 0; i <= 52; ++i)
    if (d[i]) {
        if (k & 1)  res ^= d[i];
        k >>= 1;
    }

线性基的删除

由于考的不是很多，再加上那篇博客讲得不是很清楚，因此没学。

一些例题

给带权的一些数，求最大权二进制线性无关组。

解决这种问题的常见方法还是贪心：

反正线性基的数量唯一，就把元素按权从大到小排序，挨个插进去，能插进去就计入答案。这样保证答案最大。

需要线段树分治，详见：线段树分治