我们称一个线性空间 $V$ 的一个极大线性无关集为这个线性空间的线性基，简称基。

异或线性基

在异或空间下，我们定义如下内容。

异或和

设 $S$ 为一无符号整数集，定义其异或和 $sum(S)=S_1\oplus S_2\oplus\ldots\oplus S_{|S|}$。

张成

设 $T \subseteq S$ ，所有这样的子集 $T$ 的异或和组成的集合称为集合 $S$ 的张成，记作 $\operatorname{span}(S)$ 。即，在 $S$中选出任意多个数，其异或和的所有可能的结果组成的集合。

线性相关

对于一个集合 $S$ ，如果存在一个元素 $S_j$ ，使得， $S$ 在去除这个元素后得到的集合 $S^{\prime}$ 的张成 $\operatorname{span}\left(S^{\prime}\right)$ 中包含 $S_j$ ，即， $S_j \in \operatorname{span}\left(S^{\prime}\right)$ ，则称集合 $S$ 线性相关。

更形象地，可以表示为，存在一个元素 $S_j$ ，可以用其它若干个元素异或起来得到。
即存在一个子集 $T \subseteq S$，满足 $sum(S)=0$。

相对的，如果不存在这样的元素 $S_j$，则称集合 $S$ 线性无关。

一个显然的结论是，对于这个线性相关的集合 $S$ ，去除这个元素后，张成的集合不变。

性质

• 原序列的任意一个数都可以由线性基中唯一的一些数异或得到；
• 线性基内部任意数字异或起来不为 $0$（线性无关）；
• 线性基是极小的满足线性基性质的集合，它的任何真子集都不可能是线性基；

构造 - 贪心

这种方法是在线的。

设 $a$ 表示线性基数组，我们插入一个数字 $x$ 时，从高位到低位枚举：

• 若 $x$ 的当前位置为 $0$，则当前位比最高位高，直接考虑下一位；
• 若当前位置 $a_i$ 的值为 $0$，显然 $a_{1}\sim a_{i}$ 无法表示出 $x$，即 $x$ 是基中的数字，$a_i \gets x$，插入完成；
• 若 $a_i\neq 0$，则 $x\gets x\oplus a_i$，即使用 $a_i$ 将最高位去除，重复上述操作。

代码实现

void insert(int x) {
	for (int i = 63; i >= 0; i -- ) {
		if (x >> i & 1) {
			if (!a[i]) return a[i] = x, void();
			else x ^= a[i];
		}
	}
}

构造出线性基的性质：

• 线性基的基本性质。
• 线性基中各数二进制最高位不同。

如果使用上面的的做法构造线性基，解决子集异或最大值问题则需要再套一层贪心，求 $k$ 小值则相对困难。

容易发现对于线性基中两个元素 $x$, $y$，将 $y$ 替换为 $x \oplus y$ 依然是一组基。

于是我们将插入操作修改：

void insert(int x) {
	for (int i = 60; ~i; i -- ) {
		if (!(x >> i & 1)) continue;
		if (!a[i]) {
			for (int j = i - 1; ~j; j -- ) if (x >> j & 1) x ^= a[j];
			for (int j = i + 1; j <= 60; j ++ ) if (a[j] >> i & 1) a[j] ^= x;
			return a[i] = x, void();
		}
		else x ^= a[i];
	}
}

容易发现其满足如下性质：

$a_i=0$ ，并且

• 只有满足 $j>i$ 的 $a_j$（即，位于 $a_i$ 后面的所有 $a_j$）的第 $i$ 个二进制位可能为 $1$。

$a_i \neq 0$ ，并且

• 整个 $a$ 数组中只有 $a_i$ 的第 $i$ 个二进制位为 $1$；
• $a_i$ 更高的二进制位（$>i$ 的二进制位）一定为 $0$；
• $a_i$ 更低的二进制位（$<i$ 的二进制位）可能为 $1$；

我们称第 $i$ 位存在于线性基中，当且仅当 $a_i \neq 0$。

我们现在构造出的线性基又多了一条性质：

$$\forall i>j, a_i\oplus a_j>a_i$$

考虑二进制数的性质：选择高位上的 $1$ 一定比不选高位上的大。
类似的，我们构造的线性基满足：选择「控制较高位上 $1$ 的元素」一定比不选的异或和大。
这与二进制数的性质一致

于是我们对于求子集第 $k$ 小异或和 $ans$：

• 若存在插入失败的情况，相当于求 $k-1$ 小的非零异或和。
• 初始时 $ans \gets0$，我们取出线性基中 $a_i \neq 0$ 的位置，放入序列 $b$ 中；
• 若 $k$ 的第 $i$ 位为 $1$，$ans \gets ans\oplus b_i$。

例题：HDU3949 XOR

插入和查询的复杂度均为 $O(\log_2 n)$。

构造 - 高斯消元

直接消元即可。

int r = 1;
for (int c = 63, t = r; r <= n && ~c; c -- , t = r) {
	for (int i = r; i <= n; i ++ ) if (a[i] >> c & 1) t = i;
	if (!(a[t] >> c & 1)) continue;
	swap(a[t], a[r]);
	for (int i = 1; i <= n; i ++ ) {
		if (i == r) continue;
		if (!(a[i] >> c & 1)) continue;
		a[i] ^= a[r];
	}
	r ++ ;
}

高斯消元构造出的线性基与修改后的贪心构造出的线性基性质相同。

带修（删）线性基 - 离线

PYYZOJ 42. 最大割

设一个点的权值为与它相连的边的权值的异或和。容易发现一个子集的权值等于选出点的权值的异或和。

那么问题转化为从 $n$ 个点中选出若干个点，最大化选出点权值的异或和，动态加边可以转化为动态修改两个点的权值。

线段树分治维护每一个点每个权值出现的时间段即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define fir first
#define sec second
#define ep emplace
#define eb emplace_back

#define lowbit(x) ((x) & (-(x)))

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 1010;

int n, m, ans, l, L = 1000, tim[N];
bitset<N> g[N], bt[N * 3];
vector<int> tr[N << 2];
char s[N];

class Basis {
private:
	bitset<N> t[N];
public:
	void insert(bitset<N> x) {
		for (int i = L; ~i; i -- ) {
			if (x[i]) {
				if (!t[i][i]) return t[i] = x, void();
				else x ^= t[i];
			}
		}
	}

	bitset<N> queryMax() {
		bitset<N> res;
		for (int i = L; ~i; i -- ) if (!res[i]) res ^= t[i];
		return res;
	}
} now;

void modify(int u, int l, int r, int ql, int qr, int id) {
	if (ql <= l && r <= qr) return tr[u].eb(id), void();
	int mid = (l + r) >> 1;
	if (ql <= mid) modify(u << 1, l, mid, ql, qr, id);
	if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, id);
}

void solve(int u, int l, int r) {
	Basis backup = now;
	for (int id : tr[u]) now.insert(bt[id]);
	if (l == r) {
		bitset<N> ans = now.queryMax();
		bool flag = false;
		for (int j = L; ~j; j -- ) {
			flag |= ans.test(j);
			if (flag) printf("%d", ans.test(j));
		}
		puts(flag ? "" : "0");
		return now = backup, void();
	}
	int mid = (l + r) >> 1;
	solve(u << 1, l, mid), solve(u << 1 | 1, mid + 1, r);
	now = backup;
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i ++ ) tim[i] = 1;
	for (int i = 1; i <= m; i ++ ) {
		int a = read(), b = read();
		scanf("%s", s + 1), l = strlen(s + 1);
		bitset<N> w;
		for (int j = l - 1; j >= 0; j -- ) w[j] = (s[l - j] == '1');
		if (tim[a] < i) modify(1, 1, m, tim[a], i - 1, i * 2 - 1);
		if (tim[b] < i) modify(1, 1, m, tim[b], i - 1, i * 2);
		bt[i * 2 - 1] = g[a], bt[i * 2] = g[b];
		g[a] ^= w, g[b] ^= w, tim[a] = tim[b] = i;
	}
	for (int i = 1; i <= n; i ++ ) {
		modify(1, 1, m, tim[i], m, 2 * m + i);
		bt[2 * m + i] = g[i];
	}
	solve(1, 1, m);
	return 0;
}

实数线性基

高斯消元即可。