线性基常用来解决子集异或问题，可用来求解 “集合元素异或第k大” 问题

异或和、张成、线性相关、线性基的定义与性质和构造方法均可以参考 这篇博客)

本文记录我对线性基的理解，线性基本质上就是简化版高斯消元，高斯消元求得是标准化线性基或者叫简化基，即如果一个位置上的数字是1，就会把这一列的1全部消掉，与之相对地，称之为非标准线性基或者部分线性基，标准化线性基是唯一地，而非标准线性基不唯一，线性基包括简化基和部分线性基，网上的线性基构造方法其实就是高斯消元的替代版本。

线性基的优势：

  1. 支持动态插入，而高斯消元只能求一次
  2. 代码量短

构造标准线性基的方法：

  1. 高斯消元（a集合就是标准线性基）
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
#include <bits/stdc++.h>
using ull = unsigned long long;
const int MAXN = 1e5 + 5;

ull deg(ull num, int deg) { return num & (1ull << deg); }

ull a[MAXN];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%llu", &a[i]);
  int row = 1;
  for (int col = 63; ~col && row <= n; --col) {
    for (int i = row; i <= n; ++i) {
      if (deg(a[i], col)) {
        std::swap(a[row], a[i]);
        break;
      }
    }
    if (!deg(a[row], col)) continue;
    for (int i = 1; i <= n; ++i) {
      if (i == row) continue;
      if (deg(a[i], col)) {
        a[i] ^= a[row];
      }
    }
    ++row;
  }
  ull ans = 0;
  for (int i = 1; i < row; ++i) {
    ans ^= a[i];
  }
  printf("%llu\n", ans);
  return 0;
}
  1. 根据标准线性基的性质直接构造
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
const int MAXL = 60;

struct LinearBasis
{
    long long a[MAXL + 1];

    LinearBasis()
    {
        std::fill(a, a + MAXL + 1, 0);
    }

    void insert(long long t)
    {
        // 逆序枚举二进制位
        for (int j = MAXL; j >= 0; j--)
        {
            // 如果 t 的第 j 位为 0，则跳过
            if (!(t & (1ll << j))) continue;

            // 如果 a[j] != 0，则用 a[j] 消去 t 的第 j 位上的 1
            if (a[j]) t ^= a[j];
            else
            {
                // 找到可以插入 a[j] 的位置

                // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
                // 如果某一个 a[k] = 0 也无须担心，因为这时候第 k 位不存在于线性基中，不需要保证 t 的第 k 位为 0
                for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k];

                // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
                for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ll << j)) a[k] ^= t;

                // 插入到 a[j] 的位置上
                a[j] = t;

                // 不要忘记，结束插入过程
                return;
            }

            // 此时 t 的第 j 位为 0，继续寻找其最高位上的 1
        }

        // 如果没有插入到任何一个位置上，则表明 t 可以由 a 中若干个元素的异或和表示出，即 t 在 span(a) 中
    }
};

P3812 【模板】线性基（求最大异或）

原题链接](https://www.luogu.com.cn/problem/P3812))

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXL = 64;
ll a[64];

void insert(ll val) {
	for (int i = MAXL - 1; i >= 0; i--) {
		if (!((val >> i) & 1)) continue;
		if (a[i]) val ^= a[i];
		else {
			for (int j = 0; j < i; j++) {
				if (val >> j & 1) {
					val ^= a[j];
				}
			}
			for (int j = i + 1; j < MAXL; j++) {
				if (a[j] >> i & 1) {
					a[j] ^= val;
				}
			}
			a[i] = val;
			break;
		}
	}
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		long long t;
		cin >> t;
		insert(t);
	}
// 	for (int i = 0; i < MAXL; i++) cout << a[i] << ' ';
// 	cout << endl;
	ll ans = 0;
	for (int i = 0; i < MAXL; i++) ans ^= a[i];
	cout << ans;
	return 0;
}

Acwing 210.异或运算（求第k大）

原题链接

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
88
89
90
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXL = 64;
ll a[64];

void insert(ll val) {
	for (int i = MAXL - 1; i >= 0; i--) {
		if (!((val >> i) & 1)) continue;
		if (a[i]) val ^= a[i];
		else {
			for (int j = 0; j < i; j++) {
				if (val >> j & 1) {
					val ^= a[j];
				}
			}
			for (int j = i + 1; j < MAXL; j++) {
				if (a[j] >> i & 1) {
					a[j] ^= val;
				}
			}
			a[i] = val;
			break;
		}
	}
}

void solve() {
	memset(a, 0, sizeof a);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		long long t;
		cin >> t;
		insert(t);
	}
	int tail = 0;
	for (int i = 0; i < MAXL; i++) {
		if (a[i]) {
			a[tail++] = a[i];
		}
	}
//	cout << "a[i]" << endl;
//	for (int i = 0; i < tail; i++) {
//		cout << a[i] << " ";
//	}
//	cout << endl;
	
	int flag = 0;
	if (n > tail) {
		flag = 1;
	}
	int q;
	cin >> q;
	while (q--) {
		long long k;
		cin >> k;
		if (flag) {
			k--;
		}
		if (k == 0) {
			cout << 0 << endl;
			continue;
		}
		ll ans = 0;
		for (int i = 63; i >= 0; i--) {
			if (k >> i & 1) {
//				cout << "test: " << k << " " << i << endl;
				if (i >= tail) {
					ans = -1;
					break;
				}
				ans ^= a[i];
			}
		}
		cout << ans << endl;;
	}
}

int main() {
	int T;
	cin >> T;
	int t = 1;
	while (T--) {
		cout << "Case #" << t++ << ":" << endl;
		solve();
	}
	return 0;
}