跳转至

线性基

引入

首先对于普通的线性基定义如下：

定义

对于一个在 \(n\) 维平面上的点集 \(V\)，如果对于一个集合 \(W\)，而对于 \(V_i\) 都可以表达为 \(V_i = a \cdot W_1 + b\cdot W_2 \cdots\) 。

那么称 \(W\) 是 \(V\) 的一个线性基。

容易发现，线性基大小一定小于等于 \(n\) ，因为可以构造出 \(\{\{1, 0, 0, 0\cdots\}, \{0, 1, 0, 0\cdots\}, \{0, 0, 1, 0\cdots\}\cdots\}\) 。

那么我们可以找出两种实现求出线性基的做法：

高斯消元法

首先这个办法能够达到：

  • 产生线性基大小小于等于 \(n\) 。

  • 线性基元素从大到小排序

  • 对于线性基中的每一个元素的最高位不重复

那么对于高斯消元，我们发现其与线性基有许多相似之处。因为当对于高斯消元的一行直接加权之后减去另一行。那么其实也只需要满足剩下的那个矩阵的线性基就可以了。

所以我们可以构造出对于前面 \(n \times n\) 的矩阵，只有对角线有数，那么此时一定满足要求。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
double a[N][M];
int gauss() {
    int k=1;
    for(int i=M; i>=0; i--) {
        for(int j=k; j<=n; j++) 
            if(a[j][i]) {
                swap(a[k], a[j])
            }
        if(a[k][i] == 0) continue;

        for(int j=1; j<=n; j++) {
            if(j == k) continue;
            double t = a[j][i] / a[k][i];
            for(int u=1; u<=M; u++) a[j][u] -= a[k][u]*t;
        }

        if(k++ == n) break;
    }
    return k-1;
}

贪心法

首先这个方法能够达到：

  • 产生线性基大小小于等于 \(n\)

  • 线性基元素从小到大排序

  • 最高位元素不重复（注意和前面的不同）

那么为了达到这个效果，我们只需要对于每一个新插入的 \(x\) ，然后便利所有不为 \(0\) 的位置，如果当前线性基对应位置为 \(0\) 直接对一次位置插入 \(x\) ，否则把 \(x\) 异或等于当前线性基位置（为了维护条件 \(3\)）

重要之处

这个贪心法对于不同的插入顺序，得到的结果是不同的，仅满足上面的性质

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<double> b[N];
bool insert(vector<double> x) {
    for(int i=M; i>=1; i--) {
        if(fabs(x[i]) < eps) continue;
        if(fabs(b[i][i]) < eps) {
            b[i] = x;
            return 1;
        }
        double t = x[i] / b[i][i];
        for(int j=1; j<=M; j++)
            x[j] -= b[j][i] * t;
    }
    return 0;
}

注意这里返回值有一个 \(1/0\) ，这个表示是否插入成功，如果插入失败，代表线性基中的元素已经可以组成 \(x\) 。

异或线性基

一般来是，题目更多偏向异或线性基， 即所有元素能被线性基中的元素异或得到。

其中他两部分代码如下：

高斯消元法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int b[64];
int gauss(int n) {
    int k=1;
    for(int i=62; i>=0; i--) {
        for(int j=k; j<=n; j++) 
            if(b[j] & (1ll<<i)) {
                swap(b[j], b[k]);
                break;
            }
        if(!(b[k] & (1ll<<j))) continue;
        for(int j=1; j<=n; j++) 
            if(j!=k && (b[j] & (1<<i))) b[j] ^= b[k];
        if(k++ == n) break;
    }
    return k-1;
}

贪心法：

1
2
3
4
5
6
7
8
9
int b[64];
bool insert(int x) {
    for(int i=62; i>=0; i--) {
        if(!(x & (1ll<<i))) continue;
        if(b[i] == 0) { b[i]=x; return 1; }
        x ^= b[i];
    }
    return 0;
}

应用

首先是求解最大异或和，对于 高斯消元 由于最高位没有其他同为 \(1\) ，所以直接全部异或起来就可以了。然后对于 贪心法 ，由于最高位可能还有其他 \(1\) ，所以从大到小枚举，然后如果当前二进制位置不是 \(1\) (还有空缺)，那么就插入。

1
2
for(int i=0; i<62; i++) ans ^= b[i];
for(int i=0; i<62; i++) ans = max(ans, ans ^ b[i]);

然后看几个例题：

P4570 [BJWC2011] 元素

首先如果需要考虑放进去是否能够塞满，那么考虑使用线性基。现在影响问题的因素就是使用 贪心法 插入的顺序。

我们考虑 $a \oplus b \oplus c = d $ , 那么 同样可以得到 \(b \oplus c \oplus d = a\) 。所以他们之中必定有一个不能被选择，那么为了解决最优，我们就让贡献小的不放进去，相当于优先放贡献大的。

P4151 [WC2011] 最大 XOR 和路径

首先考虑对于一条路径，实际上重复穿越的路径是没有作用的，那么我们可以对于一条路径，将其拆分为一个主链和其他环。当我们确定主链，那么就之间把主链和环的异或和都放在线性基中就可以知道了。

那么具体选择那一条主链呢，实际上任意一条都可以，因为当有多条简单路径可以到达终点，那么其实就是构成了一个大的环，令当前选择的路径为 \(a\) 另一个为 \(b\) ，那么相当于取 \(\max(a, a \oplus (a \oplus b) ) = max(a, b)\) 。

P11620 [Ynoi Easy Round 2025] TEST_34

区间查询，因为带修所以考虑线段树区间合并线性基，然后考虑如何区间修改。

我们考虑进行差分处理，然后考虑对于查询一个区间需要把那些元素放入线性基。

对于每一个点他当前的权值就是一个区间前缀和，那么一个区间的贡献就是全部前缀和。但是注意到异或会相互抵消，所以我们只需要对于线性基插入 \([1, l], [l+1, l+1], [l+2, l+2]\cdots\) 。容易发现每一个选择都对应一个方案（最开始那个绑定 \(l\) ，从而保证 \([1, l-1]\) 的消除情况和真实相同）。

P3733 [HAOI2017] 八纵八横

这里只需要写一个可撤销线性基（即记录持续结束时间），然后仿照 "P4151 [WC2011] 最大 XOR 和路径" 时时记录环就可以了。

前缀线性基

有的时候全部插入了之后我们需要是到一个区间信息，此时我们可以对右端点可持久化，然后当询问 \([l, r]\) 的信息时， 查询 \(r\) 对应的信息，所以此时相当于线性基要求其基的来源需要大于等于 \(l\) 。

我们考虑对于每一个基记录一个其来源的 \(pos\) ，那么我么需要让 \(pos\) 尽可能大，所以我们考虑加入一个 \(x\) 时如果经过一个 \(b_i \neq 0\) 并且 \(pos_i < p_x\) ，那么就交换 \((b_i, x), (pos_i, p_x)\) ，因为这个 \(b_i\) 对应的线性基一定是比 \(x\) 将要插入的线性基大的，因此需要优先保证 \(b_i\) 被选择。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace BAS {
    const int B = 32;

    int p;
    int b[N][B], pos[N][B];

    bool insert(int x) {
        ++p;
        for(int i=0; i<B; i++) {
            b[p][i] = b[p-1][i];
            pos[p][i] = pos[p-1][i];
        }

        int P=p;
        for(int i=B-1; i>=0; i--) {
            if(!(x & (1ll<<i))) continue;
            if(b[p][i] == 0) {
                b[p][i] = x;
                pos[p][i] = P;
                return 1;
            }

            if(pos[p][i] < P)
                swap(pos[p][i], P), swap(b[p][i], x);
            x ^= b[p][i];
        }
        return 0;
    }

    int query(int l, int r) {
        int ans=0;
        for(int i=B-1; i>=0; i--)
            if(l <= pos[r][i]) ans = max(ans, ans^b[r][i]);
        return ans;
    }
}