异或线性基

一、问题背景：为什么要引入“线性基”？

在算法竞赛中，常见的问题之一是：

给定一个数组 $a_1,a_2,\dots,a_n$，考虑所有子集的异或和（即⊕），你可能需要：

1. 求出所有子集异或和中的最大值；
2. 判断某个数是否能由这些元素的异或组合得到；
3. 求第 $k$ 大的异或和；
4. 维护动态插入、删除并查询异或值。

如果直接枚举所有子集，时间复杂度是 $O(2^n)$，显然不可行。
于是引入 线性基（Xor Basis / Linear Basis） 来高效解决。

---

二、异或与线性独立

我们把每个数看作一个二进制向量。

• 异或操作相当于向量空间里的“加法（模 2）”。
• 一组数的子集异或和，正好对应了这组向量的 线性组合。

于是问题转化为：

在二进制向量空间中，找到一个“基”来表示所有可能的组合。

这就是 线性基：

• 一组最小的、互相线性独立的向量；
• 能表示原集合中所有数的异或和。

---

三、线性基的构造

1. 核心思想

高斯消元的简化版：逐位考虑（从高位到低位），尽量把每个数的最高位独立出来。

2. 构造过程

假设整型范围为 64 位（竞赛中一般 $\leq 64$）：

const int MAX_LOG = 64;
long long basis[MAX_LOG]; // basis[i] 表示最高位为 i 的基底

void insert(long long x) {
    for (int i = MAX_LOG - 1; i >= 0; i--) {
        if (!(x >> i & 1)) continue;  // 这一位不是1
        if (!basis[i]) {              // 如果没有基底，就放进去
            basis[i] = x;
            return;
        }
        x ^= basis[i];                // 消去最高位
    }
}

性质：

• 最终得到的 basis[] 就是一组线性基；
• 集合中所有数的异或和，都能用 basis[] 的组合得到。

---

四、常见应用

1. 最大子集异或和

从高位往低位贪心取：

long long getMax() {
    long long ans = 0;
    for (int i = MAX_LOG - 1; i >= 0; i--) {
        ans = max(ans, ans ^ basis[i]);
    }
    return ans;
}

解释：

• 如果当前位能被翻转为 1，就翻转。
• 最后得到的就是最大值。

时间复杂度：$O(\log A)$，其中 $A$ 为数值范围。

---

2. 判断一个数能否由集合异或得到

同样从高位到低位尝试消元：

bool check(long long x) {
    for (int i = MAX_LOG - 1; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!basis[i]) return false; // 这一位没有基底，无法消去
        x ^= basis[i];
    }
    return true; // 可以消成 0
}

---

3. 求第 $k$ 大的异或和

技巧：

• 首先把线性基压缩成“独立向量数组” $b[1..m]$。
• 所有异或和的数量是 $2^m$。
• 第 $k$ 大可以通过构造字典序方式得到。

示例代码：

vector<long long> vec;
for (int i = 0; i < MAX_LOG; i++) {
    if (basis[i]) vec.push_back(basis[i]);
}
// vec 中是线性基向量

若需要第 $k$大：

• 排序 vec，从高位到低位；
• 用二进制展开 $k$，逐步决定是否加入某个基底；
• 时间复杂度 $O(m)$，其中 $m \leq \log A$。

---

4. 动态维护（可选）

有时题目需要支持 动态插入。

• 插入：直接用 insert(x)。
• 删除：比较复杂，一般要用 可持久化线性基 或 分治线性基。
• 区间查询：常见做法是 线性基 + 可持久化 Trie。

---

五、性质总结

1. 线性基大小不超过数值的位数（64 位整数最多 64 个）。
2. 所有子集异或和数量是 $2^m$，其中 $m$是线性基大小。
3. 最大值/最小值可以贪心得到；判断能否得到某个数用消元即可。
4. 在竞赛中广泛用于 异或最大化、可达性判定、计数问题。

---

六、举个例子

数组：([3, 5, 6])

• 二进制：

  • 3 = 011
  • 5 = 101
  • 6 = 110

• 构造过程：

  • 插入 3 → basis[1] = 3 (011)
  • 插入 5 → basis[2] = 5 (101)
  • 插入 6 → 可由 3 ^ 5 得到，不加入

• 线性基 = {3, 5}

• 所有子集异或和：{0, 3, 5, 6}

• 最大值 = 6。

---

七、第 k 大异或和完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_LOG = 64;
long long basis[MAX_LOG]; // basis[i] 表示最高位为 i 的基底
int cnt = 0;              // 线性基的大小

// 插入一个数到线性基
void insert(long long x) {
    for (int i = MAX_LOG - 1; i >= 0; i--) {
        if (!(x >> i & 1)) continue;
        if (!basis[i]) {
            basis[i] = x;
            cnt++;
            return;
        }
        x ^= basis[i];
    }
}

// 压缩线性基，得到独立向量数组
vector<long long> getVector() {
    vector<long long> vec;
    for (int i = 0; i < MAX_LOG; i++) {
        if (basis[i]) vec.push_back(basis[i]);
    }
    // 为了保证顺序，按从大到小排序
    sort(vec.begin(), vec.end(), greater<long long>());
    return vec;
}

// 求第 k 大异或和
// k 从 1 开始，k <= 2^m，其中 m = cnt
long long kthXor(long long k) {
    vector<long long> vec = getVector();
    int m = vec.size();

    // 特殊情况：k 超出范围
    if (k > (1LL << m)) return -1;

    // 从小到大枚举所有异或和
    // 第 1 小是 0，因此第 k 大 = 所有和中第 (2^m - k) 小
    k = (1LL << m) - k;

    long long ans = 0;
    for (int i = 0; i < m; i++) {
        if (k >> (m - i - 1) & 1) {
            ans ^= vec[i];
        }
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        insert(x);
    }

    int q;
    cin >> q; // 查询次数
    while (q--) {
        long long k;
        cin >> k;
        cout << kthXor(k) << "\n";
    }
    return 0;
}

---