线性基 | Vegetog's Blog

在算法竞赛中，线性基（Linear Basis）主要用于解决异或（XOR）相关问题。本文将从异或的角度出发，结合线性代数知识进行讲解。

1. 定义与性质

假设你有一大堆数字 $S = \{a_1, a_2, \dots, a_n\}$ 。这些数字可以通过异或运算（XOR）组合出成千上万个新的数字。

线性基 $B$ 就是从 $S$ 中提炼出来的一个很小的集合，它满足以下三个核心性质：

张成空间不变： $S$ 中任意子集的异或和，都可以由 $B$ 中的子集异或得到。即原本能组合出的数字，现在依然能组合出。
封闭性： $B$ 无法异或出 $S$ 异或不出来的数字。
极小性与线性无关： $B$ 是满足上述条件的最小集合。 $B$ 中的数字之间互不干扰（线性无关），即你无法用 $B$ 里的几个非空子集异或出 $0$ 。

数学直觉：这其实和线性代数中的极大线性无关组非常类似。只不过我们是在有限域 $\mathbb{F}_2$ （模 2 域）上讨论，向量的加减法变成了异或运算。

2. 核心操作：插入 (Insert)

线性基的构建过程，本质上就是高斯消元的简化版。

bool insert(int x) {
    // 从高位到低位扫描
    for (int i = P_COUNT - 1; i >= 0; --i) {
        if ((x >> i) & 1) { // 如果 x 的第 i 位是 1
            if (!basis[i]) {
                // 如果基底该位为空，则插入，成为了新的基向量
                basis[i] = x;
                return true; 
            }
            // 否则用基底消去 x 的这一位（高斯消元）
            x ^= basis[i];
        }
    }
    // 如果 x 最终变成了 0，说明 x 可以被之前的基向量异或得到
    // 即发生了线性相关，插入失败
    return false;
}

插入流程解析

当我们想把数字 $x$ 插入线性基时，就像在做一个碰撞检测：

扫描：从最高位开始向下扫描，假设 $x$ 的第 $j$ 位是 1。
判定：
- 如果 basis[j] 没人（为 0）：太好了， $x$ 可以填补这个维度的空白。令 basis[j] = x，插入成功。这意味着 $x$ 提供了新的“特征”，扩充了异或空间。
- 如果 basis[j] 有人（不为 0）：说明第 $j$ 位是 1 的特征已经被之前的某个数字代表了。
消元：执行 $x = x \oplus basis[j]$ $x = x \oplus ba s i s [j]$ 。
- 为什么要异或？ 异或相当于减法/消元。因为 basis[j] 的第 $j$ 位是 1，异或后， $x$ 的第 $j$ 位就变成了 0。我们拿着消去这一位后的残余值，继续去更低的位寻找位置。

最终结果：

情况 A（插入成功）：说明 $x$ 包含了一些线性基里原本不存在的特征（线性无关）。
情况 B（插入失败，x 变为 0）：说明 $x$ 的所有特征都被线性基里的现有数字消完了。这意味着 $x$ 可以由线性基里已有的数字异或得到。

3. 经典例题实战

题目链接：牛客竞赛永远亭的小游戏（续）

问题分析

题目要求判断区间 $[l, r]$ 内是否存在一个子序列，其乘积为完全平方数。

数学转化：
- 一个数是完全平方数 $\iff$ 其所有质因数的指数均为偶数。
- 乘积的质因数指数 = 各因子质因数指数之和。
- 关注奇偶性 $\iff$ 模 2 加法 $\iff$ 异或运算。
向量化：题目中 $a_i \le 100$ ，100 以内只有 25 个质数。我们可以把每个数字 $a_i$ 映射为一个长度为 25 的二进制向量（Mask）：
- 如果 $a_i$ 的分解中，第 $j$ 个质数的指数是奇数，则向量第 $j$ 位为 1，否则为 0。
问题等价：在区间中寻找子序列乘积为完全平方数 $\iff$ 在区间中寻找子集，使得其对应的 Mask 异或和为 0。

解题思路

大区间优化（鸽巢原理）：线性基的一个重要结论是：在一个 $k$ 维空间中，最多只能有 $k$ 个线性无关的向量。 本题维度 $D=25$ 。当区间长度 $r - l + 1 > 25$ 时，向量个数超过维度，根据鸽巢原理，这些向量之间一定存在线性相关性。即：一定能找到一个子集异或和为 0，直接输出 Yes。
小区间处理（线性基）：对于 $r - l + 1 \le 25$ 的情况，暴力取出区间内所有数的 Mask，尝试插入线性基。
- 如果某个数 插入失败（被消成 0），或者该数本身就是 0（完全平方数），说明找到了异或和为 0 的子集，输出 Yes。
- 如果所有数都 插入成功，说明它们线性无关，无法异或出 0，输出 No。

AC 代码

提交记录

// 100 以内的质数只有 25 个，这就是向量空间的维数
constexpr int N = 25;
const vector<int> pm = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    
    // 预处理：将每个数转化为二进制 Mask
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for (int j = 0; j < N; j++) {
            while (x % pm[j] == 0) {
                x /= pm[j];
                a[i] ^= (1 << j); // 记录质因数指数的奇偶性
            }
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        
        // 优化：根据鸽巢原理，超过维数必有解
        if (r - l + 1 > N) {
            cout << "Yes\n";
            continue;
        }
        
        // 小区间：暴力线性基判定
        vector<int> lb(N, 0);
        bool win = 0;
        
        for (int i = l; i <= r; i++) {
            int x = a[i];
            bool ok = 0; // 标记是否插入成功
            
            // 尝试插入线性基
            for (int j = N - 1; j >= 0; j--) {
                if ((x >> j) & 1) {
                    if (lb[j] == 0) {
                        lb[j] = x; // 插入成功
                        ok = 1;
                        break;
                    }
                    x ^= lb[j]; // 消元
                }
            }
            
            // 如果 x 变成了 0 (插入失败)，说明存在线性相关 -> 辉夜获胜
            // 注意：如果原数 x 本身就是 0 (完全平方数)，这里的 ok 也会是 0，逻辑成立
            if (!ok) {
                win = 1;
                break;
            }
        }
        cout << (win ? "Yes" : "No") << "\n";
    }
}