线性基是处理异或问题的有力工具。

基

        在一个线性空间中，如果一组向量满足以下条件：

  • 线性无关
  • 空间中的任何向量都可以由这一组向量线性表示

        则称这一组向量为线性空间的一个基。
        在异或运算中，可以这样定义一个只有异或运算的线性空间的基：

  • 线性无关：即每一个向量不能由其它向量经异或运算得到
  • 空间中的任何向量都可以由这一组向量异或得到

        则称它们为这个空间的基，或是线性基。
        现在给定n个向量，从中选取任意个数，使得它们异或和最大。这种求最大值的问题可以用线性基解决。可以发现，将这n个数化为二进制，可以得到n个向量，每一个向量的元素取值只能为0或1。如果能够求出这n个向量的极大无关组（或其等价的形式）就可以用这个向量组来表示空间中的所有向量，可以简化问题。

线性基的求法

        给定n个数，可以用下面算法来求：

  1. 遍历每一个数x，求出它们最高位1的位置i（从0开始），初始化线性基数组p每一位为0。
  2. 若p[i]为0，则p[i]=x，否则令x=x^p[i]，重新计算最高位1的位置，递归进行，直到x加入数组或x变为0。

        注意到异或运算的逆运算就是其本身，这样的话可以看出上面的过程本质上是高斯消元的过程，将矩阵化为上三角矩阵，从而得到极大无关组。
        这里的算法有一个应用：判定给定的数能否异或得到某数，方法即为先将给定的数组加入，再加入待判定的数。若该数最终加入了线性基，则不可表示，否则可表示。

最值的求法

        得到了线性基，如何求最大或最小异或和？可以发现p数组每一位最高位1是递增的，对于满秩矩阵最小值自然就是最小的非0值，不满秩即为0；而最大值可以贪心去求，算法为： 从大到小遍历p数组，若异或上p[i]可以使答案更大，则异或，否则继续。

第k小的求法

        如果需要求第k小，可以考虑先将求出来的线性基进一步转化，把每一位p[i]变成唯一的第i位为1的数。这一步可以从高位到低位遍历线性基，并向后扫，若后面的数第i位为1，则异或p[i]，这样可以将线性基化为上面的形式。之后求第k小有如下的算法：将k二进制拆分，若第i位为1，则答案异或上线性基中第i+1个不为0的数。这里需要注意0的处理。

普通模板

1
2
3
4
5
6
7
8
9
10
11
12
inline void insert(long long *s, long long p) {//将p插入线性基s
	if(p == 0)return;
    for (int i = 60; i >= 0; i--) {
        if (p & (1ll << i)) {
            if (s[i] == 0) {
                s[i] = p;
                return;
            } else p ^= s[i];
        }
    }
}

例题

        介绍一些例题，不涉及题面，点击标题可跳转。

[HDU6579]Operation

        2019第一次多校赛B题。
        本题需要动态向后面加数并且求$[l,r]$中某些数的最大值，后者是线性基能够解决的经典问题。
        对于这样的问题，我们可以考虑贪心地求前缀线性基。对于每一个前缀，维护一个线性基数组，这在$O(nlogn)$时空复杂度下可以完成。
        在加入一个数后，我们希望靠后的数能够出现在更高位的位置（贪心思想）。于是当某一位与要加入的数冲突时，如果原有的数在待加入的数左侧，那么我们不移动待加入的数，而是移动原有的数，将其挪动到更低位的位置。由于需要考虑位置关系，我们需要维护一个数组记录每一个数的位置。
        查询的时候使用线性基。从高位开始遍历，如果对应的数在区间范围内，并且异或上值更大，那么我们异或上这个值，最终得到的就是答案。
        对于新加入的数，相当于一个新的前缀，维护一下线性基就好了。总体时间复杂度$O(nlogn+mlogn)$。

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
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;
int op[1000005][31], num[1000005][31], n, m;

inline int read() {
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

int query(int x) {
    for (int i = 30; i >= 0; i--)if ((1 << i) & x)return i;
    return -1;
}

void add(int rk, int w, int pp) {
    int p = query(w);
    if (p == -1)return;
    if (op[rk][p] == 0)op[rk][p] = w, num[rk][p] = pp;
    else if (num[rk][p] < pp)add(rk, op[rk][p] ^ w, num[rk][p]), op[rk][p] = w, num[rk][p] = pp;
    else add(rk, w ^ op[rk][p], pp);
}

int main() {
//    freopen("text.in", "r", stdin), freopen("text.out", "w", stdout);
    int t = read(), lastans = 0, ans;
    while (t--) {
        n = read(), m = read(), lastans = 0, memset(op, 0, sizeof(op)), memset(num, 0, sizeof(num));
        for (int i = 1; i <= n; i++) {
            if (i > 0)for (int j = 0; j <= 30; j++)op[i][j] = op[i - 1][j], num[i][j] = num[i - 1][j];
            add(i, read(), i);
        }
        while (m--) {
            int opt = read(), l, r;
            if (opt == 0) {
                l = (read() ^ lastans) % n + 1, r = (read() ^ lastans) % n + 1, ans = 0;
                if (l > r)swap(l, r);
                for (int j = 30; j >= 0; j--)if (num[r][j] >= l && (ans ^ op[r][j]) > ans)ans ^= op[r][j];
                printf("%d\n", lastans = ans);
            } else {
                if (n > 0)for (int j = 0; j <= 30; j++)op[n + 1][j] = op[n][j], num[n + 1][j] = num[n][j];
                add(n + 1, read() ^ lastans, n + 1), ++n;
            }
        }

[SCOI2016]幸运数字

        可以说是树上路径最大异或和模板题。
        考虑到两个序列合并的线性基就是它们的线性基的合并，这给我们解决问题带来了新的思路，通过这个思路可以解决区间线性基的问题。这里对于一棵树，我们对它进行树链剖分，用线段树维护一段区间的线性基，查询时合并这些线性基。
        经过合并后可以得到树上路径线性基，求它的最大值即可。不过这种方法复杂度很高，树剖和线段树都是$logn$，线性基合并是$log^2n$，达到$O(nlog^4n)$的复杂度。
        好像还可以用点分治，复杂度比较低，不过我不会。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>

#define N 20005
using namespace std;
struct Edge {
    int next, to;
} edge[N << 1];
struct J {
    long long op[61];
} nd[N << 2], S;
int head[N], n, q, dep[N], fa[N], son[N], sz[N], top[N], DFN[N], DFNHS[N], DFNID;
long long v[N], ans;

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

inline void insert(J &s, long long p) {
    for (int i = 60; i >= 0; i--) {
        if (p & (1ll << i)) {
            if (s.op[i] == 0) {
                s.op[i] = p;
                return;
            } else p ^= s.op[i];
        }
    }
}
inline void merge(J &to, const J &a, const J &b) {
    for (int i = 0; i <= 60; i++)to.op[i] = a.op[i];
    for (int i = 60; i >= 0; i--)if (b.op[i])insert(to, b.op[i]);
}

void DFS(int x) {
    sz[x] = 1;
    int pp = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        if (dep[edge[i].to] == 0) {
            dep[edge[i].to] = dep[x] + 1, fa[edge[i].to] = x, DFS(edge[i].to), sz[x] += sz[edge[i].to];
            if (sz[edge[i].to] > pp)pp = sz[edge[i].to], son[x] = edge[i].to;
        }
    }
}

void DFS(int x, int tp) {
    DFN[x] = ++DFNID, DFNHS[DFNID] = x, top[x] = tp;
    if (son[x])DFS(son[x], tp);
    else return;
    for (int i = head[x]; i; i = edge[i].next)if (DFN[edge[i].to] == 0)DFS(edge[i].to, edge[i].to);
}

void build(int l, int r, int k = 1) {
    int mid = (l + r) >> 1;
    if (l == r)insert(nd[k], v[DFNHS[l]]);
    else build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1), merge(nd[k], nd[k << 1], nd[k << 1 | 1]);
}

void query(int l, int r, int L, int R, int k = 1) {
    if (L >= l && R <= r) {
        merge(S, S, nd[k]);
        return;
    }
    int mid = (L + R) >> 1;
    if (l > mid)query(l, r, mid + 1, R, k << 1 | 1);
    else if (r <= mid)query(l, r, L, mid, k << 1);
    else query(l, mid, L, mid, k << 1), query(mid + 1, r, mid + 1, R, k << 1 | 1);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)scanf("%lld", v + i);
    for (int i = 1, x, y; i < n; i++)scanf("%d%d", &x, &y), add(x, y), add(y, x);
    dep[1] = 1, DFS(1), DFS(1, 1), build(1, n);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y), memset(S.op, 0, sizeof(S.op));
        while (top[x] != top[y]) {
            if (dep[top[x]] > dep[top[y]])swap(x, y);
            query(DFN[top[y]], DFN[y], 1, n, 1), y = fa[top[y]];
        }
        if (dep[x] > dep[y])swap(x, y);
        query(DFN[x], DFN[y], 1, n, 1), ans = 0;
        for (int i = 60; i >= 0; i--)if ((ans ^ S.op[i]) > ans)ans ^= S.op[i];
        printf("%lld\n", ans);
    }
    return 0;
}