题解：P3812 【模板】线性基

lailai0916 · 2025-09-11 07:29:05 · 题解

参考资料

• 线性基 - OI Wiki
• Basis (linear algebra) - Wikipedia
• Zassenhaus algorithm - Wikipedia

题意简述

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

解题思路

思想

将每个整数视作 \mathbb{Z}_2^k 中的一个 k 维向量。

在 \mathbb{Z}_2 上，加法 + 等价于按位异或 \oplus。

因此，问题可转化为：给定 n 个向量，选择若干个相加，使结果的二进制数值尽可能大。

在线性代数中，这组向量张成一个线性空间。

我们构造它的 线性基（一组两两线性无关且能生成整个空间的最小集合），再利用线性基“高位优先”的结构，贪心求出最大异或值。

构造

维护数列 p_i，其中 p_i 表示最高位在第 i 位为 1 的基向量（若不存在则为 0）。

插入整数 x 的过程如下：从高位到低位依次检查，如果 x 的第 i 个二进制位为 1：

• 若 p_i=0，说明这一位还没有基向量，将 p_i\gets x，并结束插入；
• 否则，将 x\gets x\oplus p_i，把第 i 位消为 0，继续向更低位处理。

若最终 x=0，说明它可以由已有基向量异或得到（线性相关），无需加入基向量。

查询

令 s=0，从高位到低位依次判断，尝试用基向量 增大 答案：

证明

数列 p 始终是一组能够张成原集合的基：

• 所有非零 p_i 的主元位互不相同，形成阶梯形结构；
• 任一已处理元素都可以由当前 p 表示（要么成为新的基向量，要么被完全消去）。

从高位到低位的顺序保证：

• 处理到第 i 位时，更高位已确定且最优；
• 若可以通过某个 p_i 使第 i 位从 0 变为 1，结果必然更优；
• 这种操作不会影响更高位，低位仍可自由调整。

因此该贪心过程能得到全局最优解。

参考代码

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

using ull=unsigned long long;
const int N=64;
ull p[N];
void insert(ull x)
{
    for(int i=N-1;i>=0;i--)
    {
        if(x>>i&1)
        {
            if(!p[i])
            {
                p[i]=x;
                return;
            }
            x^=p[i];
        }
    }
}
ull query()
{
    ull res=0;
    for(int i=N-1;i>=0;i--)
    {
        res=max(res,res^p[i]);
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        ull t;
        cin>>t;
        insert(t);
    }
    cout<<query()<<'\n';
    return 0;
}