线性基学习笔记

又是在网上搜不到讲的比较清楚的博客的算法…虽然没找到写的好的博客，但结合若干篇写的不算太差的博客，勉强是学会了..

线性基在 OI 中特指集合为若干个非负整数，运算为异或的线性基，通常用来处理一些异或相关的问题。

线性空间

百度百科说的就非常详细了，请完整阅读一遍。

3b1b 的视频也很不错，如果不了解线性代数相关知识可以看一看。（如果打不开可以尝试复制网址打开）

线性基的定义

下文中的“线性基”均指 OI 中“线性基”的常见意思。

线性基所在的线性空间

元素集合：若干个非负整数（线性基可以说是关于若干个非负整数的，在有的教程中称其为“异或集合”）。
数域： $\{0,1\}$（也就是说，线性组合是选择一个子集异或起来，$0$, $1$ 就分别代表不选或选某个元素）。
元素间运算：异或。
数乘：普通的数乘。

线性基

线性基就是上文所述的线性空间的一组基底，它具有以下性质：

在线性基中任取若干个元素，它们的异或不为零。即它们线性无关。
其所在线性空间中每个元素都有唯一的方案由线性基中元素异或得到。
选取线性基中若干个元素异或起来得到一个元素，用这个元素去替换原线性基中任意一个元素，得到的新线性基张成的空间不变。

可以发现这就是线性空间基底的性质和线性基所在线性空间的定义合在一起。

线性基的构造

构造出的线性基额外满足的性质

线性基中的每个元素的二进制最高位均不同，并且，我们称二进制最高位为第 $i$ 位的元素称为“线性基的第 $i$ 位”。

这个性质在构造和实际应用中非常方便，但要注意，它并不是线性基所在线性空间的基底所满足的必要条件。然而下文所述线性基均满足此性质，因为它真的很实用。

构造方式

我们考虑如何在已有一组线性基的情况下，向线性空间的元素集合中插入一个元素。

插入新的元素后，我们需要满足：

线性基张成的空间中包含新插入的元素。
线性基仍然线性无关。

具体地，我们依次考虑新插入元素的每个为一的二进制位，若线性基不存在这一位，那么将这个新元素加入线性基中。

否则，将新元素异或上线性基的这一位，然后继续处理下一位。

因为插入一个元素等同于插入其异或上线性基中的一个元素，所以性质一满足。

从构造过程中就可以看出，已有线性基无法异或得到这个新元素，所以性质二满足。

参考代码：

// p[i] 表示线性基的第 j 位

for (i = 1; i <= n; ++i)
{
    cin >> x;
    for (j = 60; ~j; --j)
    {
        if (((x >> j) & 1))
        {
            if (p[j]) x ^= p[j];
            else
            {
                p[j] = x;
                break;
            }
        }
    }
}

线性基的经典应用

判断一个数能否由若干数的子集异或得到

假装你要把它插入到线性空间的元素集合中，看线性基是否需要新增元素即可。

最大子集异或和

求出线性基，依次考虑线性基的每一位，若异或上能让答案更大（即答案的这一位为零）就异或上。因为如果不异或上，这一位就是零，无论后面的位如何，都比这一位为 $1$ 劣。

Luogu P3812 【模板】线性基

第 $k$ 小子集异或和

需要构造特殊的线性基，满足线性基中有的位都只在线性基中的一个数中出现。例如：原线性基为 1100 和 0111，这时线性基中有 $2,3$ 两位，而第二位（$2^2$ 这一位）在 1100 和 0111 中都出现了，所以应该修改为 1011 和 0111。

这可以用一个类似于高斯消元的过程完成：处理第 $i$ 位时，依次考虑每个比 $i$ 小的线性基中的位，若第 $i$ 位的该二进制位为 $1$ 就异或这一位。除了先用普通方法构建线性基再转化，也可以在构建时就进行处理（详见代码）。无论哪种方式，复杂度都会再乘上一个额外的二进制位数。

得到这样一个具有特殊性质的线性基后，就可以构造第 $k$ 小子集异或和了：把 $k$ 二进制拆分，每一位的 $0$ / $1$ 对应异或时选 / 不选线性基存在的这一位（比如说，二进制位的 $2^3$ 位对应线性基中第四小的存在的位）。证明也很简单，线性基中存在的位的 0/1 唯一确定了一个异或出的数，由于每个位只在一个基中为 $1$，这些位组成的二进制数的大小就可以代表异或出的数的大小。

LOJ #114. k 大异或和，毒瘤题，先不说题目名是假的，这个“非空集合”的限制非常的无聊..$0$ 本来就是线性基的线性组合之一，非要选“非空集合”，就得判一下给你的数中有没有能被其它线性基表示的数，实际上判一下线性基中元素个数是否为 $n$ 即可。

参考代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;

const int N = 100010;

int n, m, cnt;
ull p[60], a[60];

int main()
{
    int i, j;
    ull x, k;

    scanf("%d", &n);

    for (i = 1; i <= n; ++i)
    {
        scanf("%llu", &x);
        for (j = 51; ~j; --j)
        {
            if ((x >> j) & 1)
            {
                if (p[j]) x ^= p[j];
                else
                {
                    for (k = j - 1; ~k; --k) if ((x >> k) & 1) x ^= p[k];
                    for (k = j + 1; k <= 60; ++k) if ((p[k] >> j) & 1) p[k] ^= x;
                    p[j] = x;
                    break;
                }
            }
        }
    }

    for (i = 0; i <= 51; ++i) if (p[i]) a[cnt++] = p[i];

    scanf("%d", &m);

    while (m--)
    {
        scanf("%lld", &k);
        if (k >= (1ull << cnt) + (cnt != n))
        {
            puts("-1");
            continue;
        }
        if (cnt != n) --k;
        for (x = i = 0; i < cnt; ++i)
        {
            if ((k >> i) & 1ull)
            {
                x ^= a[i];
            }
        }
        printf("%llu\n", x);
    }

    return 0;
}

一些例题

[SCOI2016]幸运数字，由于不带修，倍增维护线性基即可。用点分治可以一个 log 解决。

[BJWC2011]元素，贪心，从大到小判断是否能加入线性基。

[JLOI2015]装备购买，和上一题基本一样，就是把异或换成高斯消元。

[CQOI2013]新Nim游戏，结合 Nim 游戏经典结论，还是和上面两题一样的。

[WC2011]最大XOR和路径，异或的结果必然是一条链异或上若干个环，找出任意一条链以及只含一条返祖边的环即可线性基解决。

shallot，线段树分治维护线性基。

文章目录