题解：P3812 【模板】线性基

_Weslie_ · 2025-06-18 16:30:35 · 题解

线性基的定义

称线性空间 V 的一个极大线性无关组为 V 的一组 Hamel 基或线性基，简称基。（摘自 OI Wiki）

异或线性基，换句话说，就是最大的异或和不为 1 的子集。

线性空间 V 的线性基是不唯一的。

本题目要求我们求异或线性基。那么我们接下来介绍一下异或线性基的求法。

高斯消元法

过程

前置知识：高斯消元。

高斯消元法即把每个数化为二进制表示，然后用高斯消元法消成线性基。

例如：对于序列 \{7,5,9,2\}。

我们先把这四个数分别转化为二进制矩阵。

然后对这个矩阵进行高斯消元。

消元步骤如下：

1. 从高到低位枚举。由于要通过二进制算数，我们尽量把位数从 0 开始从右往左以此递增。
2. 确定主元。假设枚举到了第 i 位，我们需要找到一个该位为 1 的数。
3. 对其他的数：假如这个数第 i 位为 1，那就让这个数异或主元，让这一位变成 0。

例如，上面的矩阵。

第一步，枚举位数 i=3（该位的值为 2^3）。确定 9 为主元。

其他元素在这一位上全部为 0，所以不必异或。

接下来枚举 i=2。由于第一个主元已经确定了，所以我们从后面的数选。

其中红色为主元，蓝色为已确定。

然后开始异或，元素 7 需要被元素 5 异或。得到：

其中紫色的元素被改变。

然后：枚举 i=1。确定主元为 2。异或另外一个 2。

现在我们就得到了一个线性基了。

优点

高斯消元后的矩阵是一个行简化阶梯形矩阵。这意味着，给定一些数，选其中一些异或起来，求异或最大值，使用高斯消元法构造线性基后直接将线性基中所有元素都异或起来输出即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long a[105],n,p[105],k;
const int bit=51;
void insert(){
    for(int i=bit;i>=0;i--){
        for(int j=k;j<n;j++) // 把当前第 i 位是 1 的数换上去
            if((p[j]>>i)&1){swap(p[j],p[k]); break;}

        if(((p[k]>>i)&1)==0) continue; // 当前第 i 位所有数都是 0    
        for(int j=0;j<n;j++) // 把其他数的第 i 位全部消为 0
            if(j!=k&&((p[j]>>i)&1)) p[j]^=p[k]; // 基的个数 +1
        k++; 
        if(k==n) break;
    }
}

long long ans=0;
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        p[i]=a[i];
    }
    insert();
    for(int i=k;i>=0;i--){
        ans^=p[i];
    }
    cout<<ans;
    return 0;
}

复杂度分析

insert 函数的复杂度是 \operatorname{O}(n\log W) 的（其中 W 是值域）。总复杂度也是 \operatorname{O}(n\log W)。

贪心法

过程

每读到一个数，就插入进来，插入的时候按照以下步骤：

1. 从高往低枚举。
2. 如果这一位是 1，那么看这一位线性基上是否有数。如果有，就异或这个数，然后接着寻找；反之，则直接把线性基的这个位置赋值为这个数。

我们来个例子。还是 \{7,5,9,2\}。

首先，p 从 2^3 位到 2^0 位分别是 \{0,0,0,0\}。插入 7，得到 \{0,7,0,0\}。

然后插入 5。5 先在 2^2 位碰到 7，异或之后变成 2。2 要插入在 2^1 位上。得到 \{0,7,2,0\}。

然后插入 9。得到 \{9,7,2,0\}。

最后的 2 在 2^1 位上遇到 2，异或之后变为 0，最终流掉。

得到的线性基是 \{9,7,2,0\}。显然这和高斯消元得到的线性基不同。

贪心法求最大值时，需要对线性基求前缀最大值，具体来说，枚举到第 i 位时，需要用前缀的异或最大值去异或 i，更新新的最大值。例如到 2^1 位，前缀最大异或值位 14，异或 2 就不如不异或。所以一定要这么做。

优点

1. 贪心法码量略小（也没小多少）。
2. 贪心法可以按顺序增添线性基。

代码

#include<bits/stdc++.h>
using namespace std;
long long a[105],n,p[105];
const int bit=63;
void insert(long long now){
    for(int i=bit;i>=0;i--){
        if(!(now>>(long long)i))continue;
        if(!p[i]){
            p[i]=now;
            break;
        }
        now^=p[i];
    }
}
long long ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        insert(a[i]);
    }
    for(int i=bit;i>=0;i--){
        if((ans xor p[i])>ans)ans^=p[i];
    }
    cout<<ans;
    return 0;
}

复杂度分析

虽说贪心法一次插入仅为 \operatorname{O}(\log W) 的复杂度，但是每输入一个数都要插入一次，所以总复杂度是 \operatorname{O}(n\log W) 的。

这就是线性基的两种求法。