线性基

解决异或问题除了字典树，剩下很常用的就是线性基。理解线性基的作用就是极大线性无关向量组，只不过在线代中我们一般讨论的是线性加减运算，而在竞赛中往往是异或运算。

对于一个向量能不能在当前的基中表示，也就是它能不能被基的某个子集异或出来，那我们如何简单高效的判断呢。首先最暴力的是直接按位拆开，高斯消元，对于每一列，也就是每一位只保留1行有1.

设原集合为S,线性基为B。线性基的性质：

  • B是极小的满足线性基性质的集合，它的任何真子集都不可能是线性基；B是线性无关的
  • S中的任意元素都可以唯一表示为 中若干个元素异或起来的结果。

直接给出最优算法：

设集合 S中最大的数在二进制意义下有 L位，我们使用一个 大小为Ld的a数组 来储存线性基。

首先，线性基是动态构造的，我们只需要从空的a 开始，每次考虑在一个已存在的线性基中插入一个数t 即可。

从 t最高位上的 1开始考虑，设这是第 j位.

  • 如果这一位已经存在于线性基中，则我们需要将t 中的这一位消掉（将 t异或上 $a_{j}$），才可以继续插入（因为只有 $a_{j}$ 的第 j位可以为 1）,然后看有1的次高位。
  • 如果这一位不存在于线性基中，则可以将 t插入到 $a_{j}$的位置上，但插入时需要保证：

image-20240412212424679

  • 第一条性质：当前经过不断被异或的t，终于找到了线性基中没有1的这位，于是插入，此时比j高的位要么原先的t的一位本身就是0，要么是1但被消掉了。

  • 我们希望保持每一位只有一个数是1，其他数是0。为了维护这个性质，我们需要继续改造t，t的低位（比j低）可能有1，影响原先的线性基的性质，所以为了继续维护这个良好的性质，我们需要继续遍历低位，如果当前t的第k位为1，并且线性基这一位不空，将 t异或上 $a_{k}$

  • 根据以上两条最终的t已经形成了，但是我们在第二条的时候考虑了t的插入对线性基的影响，现在应该考虑那那些掌握线性基高位的数对第j位的影响。我们遍历线性基的高位部分，如果高位h的第j位有1，但显然它是掌握h的，那么就让$a_{h}$^t 消除第j位的影响。

    总结算法流程如图·.

    最终线性基长什么样？这个只保证了最高位的1唯一，最低位可能有1，因为可能当前这一位就没有代表元，构造的过程中就没有被消除。

    image-20240412214027479

1.求任意子集异或的最大值：由于我们维护了每一位只有一个数有1的性质，我们只需要将所有线性基中的数异或起来是不会亏的

2.求任意求任意子集异或的最小值：如果本身线性相关就是0，本身线性无关就是最小为1位的主元

3.查询x能不能被集合表示：直接将x插入线性基中，如果插入失败，说明能被表示。

4.查询第k小的值：首先要注意存不存在第0小以及本身集合能不能异或出0，上面这两个细节四种情况都需要提前想清楚。我们就思考普通情况

5.外部查询：给定一个x，求与任意子集异或的最大值。由于任何一个子集都能被线性基表示，所以我们只需要考虑要不要选每一位线性基即可，显然从高到低位贪心。对于第j位，$x=max(x,x\oplus a[j])$

  • 很明显，构造线性基的复杂度是$O(nloga_{i})$的，其中n为插入数的个数$a_{i}$为插入的数。

但是，当$a_{i}$很大（比如说$2^{1000}$级别）的时候，你就不得不使用bitset来代替，此时复杂度就是$O(n \frac{\log^2a_{i}}{w})$，其中w是bitset常数。bitset具体的实现在我们接下来的例题[[HAOI2017]八纵八横]中可以看到。

模板：

int qmi(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
struct linerbasis {
    static const int mxl = 30;
    int a[mxl + 1];
    int n = 0;        // 尝试插入次数
    int tot = 0;      // 线性基大小
    vector<int> tmp;  // 有效位集中

    linerbasis() {
        std::fill(a, a + mxl + 1, 0);
    }

    bool insert(int t) {
        n++;
        for (int j = mxl; j >= 0; j--) {
            int u = (t >> j) & 1;
            if (u == 0)
                continue;
            if (a[j])
                t ^= a[j];
            else {
                for (int k = 0; k < j; k++)
                    if ((t >> k) & 1)
                        t ^= a[k];
                for (int k = j + 1; k <= mxl; k++)
                    if ((a[k] >> j) & 1)
                        a[k] ^= t;
                a[j] = t;
                tot++;
                return true;
            }
        }
        return false;
    }

    int querymx(int x = 0) {  // 与x能异或出来的最大值，默认是x=0表示内部自己异或的最大值
        int ans = x;
        for (int i = mxl; i >= 0; i--) ans = max(ans, ans ^ a[i]);
        return ans;
    }
    int querymn(int x = 0) {  // 与x能异或出来的最小值，默认是x=0表示内部自己异或的最小值
        int ans = x;
        for (int i = mxl; i >= 0; i--) ans = min(ans, ans ^ a[i]);
        return ans;
    }

    void initkth() {
        static bool initialized = false;
        if (initialized)
            return;
        for (int i = 0; i <= mxl; i++) {
            if (a[i])
                tmp.push_back(a[i]);
        }
        deb(tmp);
        initialized = true;
    }
    // 第k小
    int querekthmin(int k, bool tkzo = false) {  // 第0小开始算
        initkth();
        int res = 0;
        if (tkzo == 0) {
            // 如果题目没有考虑空集，我们需要考虑能不能非空子集出现0
            if (tot == n)
                k++;
        }
        if (k >= (1LL << tot))
            return -1;
        for (int j = 0; j < tot; j++) {
            if ((k >> j) & 1)
                res ^= tmp[j];
        }
        return res;
    }
    // 值为x的下标
    int querypos(int x) {
        int l = 0, r = (1 << tot) - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (querekthmin(mid, true) >= x)
                r = mid;
            else
                l = mid + 1;
        }
        int res = qmi(2, n - tot) * l % mod + 1;
        res %= mod;
        return res;
    }
};

给定 𝑛个数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。


    int querymx(int x = 0) {  // 与x能异或出来的最大值，默认是x=0表示内部自己异或的最大值
        int ans = x;
        for (int i = mxl; i >= 0; i--) ans = max(ans, ans ^ a[i]);
        return ans;
    }

线性基学习笔记 - Troverld - 博客园 (cnblogs.com)

2020杭电多校 8K / HDU 6865 - Kidnapper’s Matching Problem （线性基、KMP） - StelaYuri - 博客园 (cnblogs.com)