线性基提高组

💡 核心思想

线性基是处理异或（XOR）相关问题的数据结构。它维护一组数的一个"基底"，使得这组数能异或出的所有值，都能由基底线性组合（异或）得到。线性基的大小不超过数的二进制位数（通常 60 位）。核心操作：插入一个数时，从高位到低位，如果当前位有基底则异或消去，否则作为新的基底。

🎯 直觉理解

想象你有一堆开关，每个开关控制一组灯。线性基就是找出"最关键"的几个开关，使得你能用它们组合出所有可能的亮灯模式。规则是：每个关键开关控制一盏其他开关都不控制的灯，这样就保证了没有冗余。

📝 算法流程

1. 初始化基底数组 p[0..MAX_LOG] 为 0
2. 插入 x：从高位到低位遍历
3. 如果 x 的第 i 位为 1：
4. 如果 p[i] == 0，则 p[i] = x，结束
5. 否则 x ^= p[i]（消去第 i 位）
6. 查询最大异或和：从高位到低位，如果 ans ^ p[i] > ans，则 ans ^= p[i]
7. 判断 x 能否被表示：尝试插入 x，如果最终 x 变为 0，则可以表示

$$\text{线性基大小} \le \lfloor \log_2(\max a_i) \rfloor + 1$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;

struct LinearBasis {
    ll p[64]; // p[i] 表示第 i 位的基底
    LinearBasis() { memset(p, 0, sizeof(p)); }
    
    bool insert(ll x) {
        for (int i = 63; i >= 0; i--) {
            if (!(x >> i & 1)) continue;
            if (!p[i]) { p[i] = x; return true; }
            x ^= p[i];
        }
        return false; // x 可以被现有基底表示
    }
    
    ll maxXor() {
        ll res = 0;
        for (int i = 63; i >= 0; i--)
            if ((res ^ p[i]) > res) res ^= p[i];
        return res;
    }
    
    bool canRepresent(ll x) {
        for (int i = 63; i >= 0; i--)
            if (x >> i & 1) {
                if (!p[i]) return false;
                x ^= p[i];
            }
        return x == 0;
    }
};

int main() {
    LinearBasis lb;
    lb.insert(1);  // 001
    lb.insert(2);  // 010
    lb.insert(4);  // 100
    cout << lb.maxXor() << endl;      // 7 (1^2^4)
    cout << lb.canRepresent(5) << endl; // 1 (1^4)
    cout << lb.canRepresent(8) << endl; // 0
    return 0;
}

⚠️ 常见坑点

📚 相关题目