一些定义
向量
向量是一个抽象的概念，简单的说就是一个有方向有大小的量。
一般地，将一个 $k$ 维向量表示为 ${a_1,a_2,\cdots,a_k}$。
下面我们研究的均为 $1$ 维向量（其实就是普通的数）
异或和
对于集合 $S={a_1,a_2,\cdots,a_m}$，异或和为 $a_1 \oplus a_2\oplus\cdots\oplus a_m$，其中 $\oplus$ 为按位异或运算。
张成
对于一个集合 $S$，它的所有子集的异或和组成的集合，称为集合 $S$ 的张成，记作 $\operatorname{span}(S)$。
表出
对于元素 $x$ 和集合 $S$，$x\notin S$，若 $S$ 的异或和为 $x$，则称 $x$ 能被 $S$ 表出，或称 $x$ 能被 $S$ 中的元素表出。
线性相关
对于一个集合 $S$，如果存在 $k\in S$，将去除元素 $k$ 后的集合记为 $S’$，若 $k\in \operatorname{span}(S’)$，则称集合 $S$ 线性相关，反之称为线性无关。
若 $k$ 能被 $S$ 中的其它元素表出，那么集合 $S$ 一定线性相关。
线性基 $(\text{Base})$
称集合 $B$ 是集合 $S$ 的线性基，当且仅当：
- $B\in \operatorname{span}(S)$
- 集合 $B$ 线性无关
线性基的基本性质：
$B$ 是极小的满足线性基的集合。任何 $B$ 的真子集都不可能成为 $S$ 的线性基。
$S$ 中的任何元素都可被集合 $B$ 中的一些元素唯一表出。
$\text{Proof:}$
假设 $x\in S,B={a_1,a_2,\cdots,a_k}$ 。
$x=a_{i_1}\oplus a_{i_2}\oplus\cdots\oplus a_{i_n} -$ ①
$x=a_{j_1}\oplus a_{j_2}\oplus\cdots\oplus a_{j_m} -$ ②
① $\oplus$ ②，得 $a_{i_1}=a_{i_2}\oplus\cdots\oplus a_{i_n}\oplus a_{j_1}\oplus\cdots\oplus a_{j_m}$，则集合 $B$ 线性相关，与线性基定义矛盾。
则假设不成立，证毕。
存在一个线性基 $B$，使得线性基 $B$ 中的每一个数在二进制下最高位互不相同，若有最高位相同的两个数 $a,b$，记 $c=a\oplus b$，删除 $a$ 或 $b$ 后插入 $c$，若还有相同的就继续操作直到没有为止。
$\text{Proof:}$
显然， $a$ 能被 $b,c$ 表出，则可以将 $a$ 删除。
$|B|\le \log_2a$
$\text{Proof:}$
由性质 $3$ 可得。
构造
对于一个集合 $S$，怎么构造线性基呢？
举个例子， $S={7,5,4}$
首先构造一张表格：
| $j=2$ | $j=1$ | $j=0$ | |
|---|---|---|---|
| $b_2$ | $0$ | $0$ | $0$ |
| $b_1$ | $0$ | $0$ | $0$ |
| $b_0$ | $0$ | $0$ | $0$ |
我们一个一个插入，首先插入 $7$，$7=(111)_2$。
$7$ 在二进制下的最高位，也就是第 $2$ 位为 $1$，则可将 $7$ 插入线性基的 $b_2$ 中，都是用二进制表示。
| $j=2$ | $j=1$ | $j=0$ | |
|---|---|---|---|
| $b_2$ | $1$ | $1$ | $1$ |
| $b_1$ | $0$ | $0$ | $0$ |
| $b_0$ | $0$ | $0$ | $0$ |
然后插 $5$，$5=(101)_2$。
首先看 $5$ 的第 $2$ 位为 $1$，但是 $b_2$ 已经有值了，那么让 $5\oplus b_2=(010)_2$，这一步的原理就参照了线性基性质 $3$。
然后看第 $1$ 位，发现是 $1$，并且 $b_1$ 还没有填，那么就将 $(010)_2$ 填在 $b_1$。
| $j=2$ | $j=1$ | $j=0$ | |
|---|---|---|---|
| $b_2$ | $1$ | $1$ | $1$ |
| $b_1$ | $0$ | $1$ | $0$ |
| $b_0$ | $0$ | $0$ | $0$ |
最后插 $4$，$4=(100)_2$。
还是同样的道理，$4$ 的第 $2$ 位为 $1$，但 $b_2$ 有值，$4\oplus b_2=(011)_2$。
$(011)_2$ 的第 $1$ 位为 $1$，但 $b_1$ 有值，$(011)_2\oplus b_1=(001)_2$。
$(001)_2$ 的第 $0$ 位为 $1$，$b_0$ 没有值，那么 $b_0=(001)_2$。
这样我们就造出了完整的线性基表：
| $j=2$ | $j=1$ | $j=0$ | |
|---|---|---|---|
| $b_2$ | $1$ | $1$ | $1$ |
| $b_1$ | $0$ | $1$ | $0$ |
| $b_0$ | $0$ | $0$ | $1$ |
$B={7,2,1}$
代码
const int maxl = 60; // 这里代表的是 a 的值域在二进制下的最大长度
ll b[65];
bool insert(ll x) {
for(int j = maxl;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue; // 这是刚刚没有提到的情况，如果当前的这一位为 0，直接跳过这一位
if(b[j] != 0) {
x ^= b[j];
}
else {
b[j] = x;
return true;
}
}
return false;
}
复杂度 $O(\log a)$。
$\text{Ex}$ 构造：$\text{Menci}$ 线性基
$\text{Menci}$ 线性基也满足线性基的性质，同时还有一些特殊性质，具体可见线性基学习笔记 | Menci’s OI Blog。
实现起来也相对简单，对于一个元素 $x$，若找到了这个元素应该插入的位置 $b_j$，那么先将 $x$ 与比 $x$ 位数小的数分别异或，前提是 $x$ 的这一位是 $1$。
然后就将比 $x$ 位数大的数与 $x$ 异或即可，前提是这些数的第 $j$ 位是 $1$。
const int maxl = 60;
ll b[65];
bool insert(ll x) {
for(int j = maxl;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue;
if(b[j] != 0) {
x ^= b[j];
}
else {
for(int k = 0;k < j;k++) {
if(((1ll << k) & x) != 0) {
x ^= b[k];
}
}
for(int k = j + 1;k <= maxl;k++) {
if(((1ll << j) & b[k]) != 0) {
b[k] ^= x;
}
}
b[j] = x;
return true;
}
}
return false;
}
复杂度 $O(\log a)$。
应用
$\text{Problem 1:}$ 给定 $n$ 个数 $a_1\sim a_n$，求从中选出任意个数所能得到的最大异或值。
对于普通的线性基，解决方案为：
ll ans = 0;
for(int j = maxl;j >= 0;j--) {
if(b[j] != 0) {
ans = max(ans, ans ^ b[j]);
}
}
对于 $\text{Menci}$ 线性基，解决方案为：
ll ans = 0;
for(int j = maxl;j >= 0;j--) {
if(b[j] != 0) {
ans = ans ^ b[j];
}
}
$\text{Problem 2:}$ 给定 $n$ 个数 $a_1\sim a_n$，求从中选出任意个数与给定数 $x$ 异或所能得到的最大异或值。
对于普通的线性基，解决方案为：
ll ans = x;
for(int j = maxl;j >= 0;j--) {
if(b[j] != 0) {
ans = max(ans, ans ^ b[j]);
}
}
对于 $\text{Menci}$ 线性基，解决方案为：
ll ans = x;
for(int j = maxl;j >= 0;j--) {
if(b[j] != 0) {
ans = ans ^ b[j];
}
}
$\text{Problem 3:}$ 给定 $n$ 个数 $a_1\sim a_n$，求从中选出任意个数所能得到的最小异或值。
对于两种线性基，答案都为线性基中的最小元素。
$\text{Problem 4:}$ 给定 $n$ 个数 $a_1\sim a_n$，求 $a_1\sim a_n$ 能组成的所有异或值的个数。
求出线性基中的元素个数 $k$，则答案为 $2^k$。
$\text{Problem 5:}$ 给定 $n$ 个数 $a_1\sim a_n$，求 $a_1\sim a_n$ 能组成的所有异或值的第 $k$ 小值。
普通线性基不可做，而 $\text{Menci}$ 线性基的解决方案为：
题目
[BJWC2011]元素
转化题意后得：在给定的集合 $S$，选取出一个线性基 $B$，使得魔力值最大。
将魔力值从大到小排序，若能插入线性基，就记入答案，否则不记，最终的答案即为最大值。
证明很显然，因为线性基的大小是一定的，对于一个没有在线性基中的元素 $x$，一定存在一个属于线性基的元素 $y$，删除 $y$ 后 $x$ 就可被放入。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll Lnf = 0x3f3f3f3f3f3f3fll;
const int Mod = 1000000007;
const int maxn = 1005;
int n;
ll num[maxn], magic[maxn], id[maxn], b[65];
ll ans;
bool compare(int i, int j) {
return magic[i] > magic[j];
}
bool insert(ll x) {
for(int j = 61;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue;
if(b[j] != 0) {
x ^= b[j];
}
else {
for(int k = 0;k < j;k++) {
if(((1ll << k) & x) != 0) {
x ^= b[k];
}
}
for(int k = j + 1;k <= 61;k++) {
if(((1ll << j) & b[k]) != 0) {
b[k] ^= x;
}
}
b[j] = x;
return true;
}
}
return false;
}
int main() {
scanf("%d", &n);
for(int i = 1;i <= n;i++) {
scanf("%lld%lld", &num[i], &magic[i]);
id[i] = i;
}
sort(id + 1, id + n + 1, compare);
for(int i = 1;i <= n;i++) {
ll x = num[id[i]], y = magic[id[i]];
if(insert(x) == true) {
ans += y;
}
}
printf("%lld\n", ans);
return 0;
}
[TJOI2008]彩灯
此题即为 $\text{Problem 4}$ ，直接求线性基即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll Lnf = 0x3f3f3f3f3f3f3fll;
const int Mod = 1000000007;
const int maxn = 55;
int n, m;
int cnt;
ll b[maxn];
char light[maxn];
bool insert(ll x) {
for(int j = n;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue;
if(b[j] != 0) {
x ^= b[j];
}
else {
for(int k = 0;k < j;k++) {
if(((1ll << k) & x) != 0) {
x ^= b[k];
}
}
for(int k = j + 1;k <= n;k++) {
if(((1ll << j) & b[k]) != 0) {
b[k] ^= x;
}
}
b[j] = x;
return true;
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1;i <= m;i++) {
scanf("%s", (light + 1));
ll x = 0;
for(int j = 1;j <= n;j++) {
if(light[j] == 'O') {
x += (1ll << (j - 1));
}
}
insert(x);
}
for(int j = n;j >= 0;j--) {
if(b[j] != 0) {
cnt++;
}
}
printf("%lld\n", (1ll << cnt) % 2008);
return 0;
}
[WC2011]最大XOR和路径
首先我们观察到一个性质，最终答案可以为 $1$ 到 $n$ 的一条简单路径，加上若干个环的值得到。因为环可以看作从这个路径上的一点出发，走完一个环后再走回到原路径中，这样路径与环之间的边会走两次，从而不会贡献在异或和中。
那么是不是需要将无向图中所有的环找出来，然后求线性基呢？但无向图中的环是指数级别，无法做到。
想想我们是如何判断一个无向图中是否有环的：每走过一点，标记一下，如果走到了有标记的点就说明有环。
那我们是否可以只用这些环？答案居然是可以！（具体证明略）
这样我们找环的时间就从指数级的复杂度降到了 $O(n)$，可以接受。
下面就需要找一条从 $1$ 到 $n$ 的简单路径了，但如果有多条路径可以选择应该选哪个？
其实任选一条就行，若有两条路径可选择，设为路径 $A$ 和路径 $B$，则 $AB$ 必然也是一个环，这个环也能被线性基表出，那么无论选 $A$ 还是选 $B$，另一个都可以通过 $AB$ 环和自己表出，故选哪条都是一样的。
由此就得到了一个十分容易实现的思路：记 $node_u$ 为 $1$ 节点走到 $u$ 节点的异或和， 且走过的路径为简单路径，这样找到环时会很容易计算出这个环的异或和。然后求出线性基并与 $node_n$ 取异或和最大值，这与 $\text{Problem 2}$ 相同，然后就解决了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll Lnf = 0x3f3f3f3f3f3f3fll;
const int Mod = 1000000007;
const int maxn = 50005;
const int maxm = 100005;
int n, m, top, head[maxn];
ll node[maxn], ans;
ll b[65];
struct Edge {
int v;
ll w;
int next;
}Edge[2 * maxm];
void insert(int u, int v, ll w) {
Edge[++top].v = v;
Edge[top].w = w;
Edge[top].next = head[u];
head[u] = top;
}
bool insert(ll x) {
for(int j = 61;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue;
if(b[j] != 0) {
x ^= b[j];
}
else {
for(int k = 0;k < j;k++) {
if(((1ll << k) & x) != 0) {
x ^= b[j];
}
}
for(int k = j + 1;k <= 61;k++) {
if(((1ll << j) & b[k]) != 0) {
b[k] ^= x;
}
}
b[j] = x;
return true;
}
}
return false;
}
void dfs(int u) {
for(int i = head[u];i;i = Edge[i].next) {
int v = Edge[i].v;
ll w = Edge[i].w;
if(node[v] != -1) {
insert(node[v] ^ node[u] ^ w);
}
else {
node[v] = node[u] ^ w;
dfs(v);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1;i <= m;i++) {
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
insert(u, v, w);
insert(v, u, w);
}
memset(node, -1, sizeof(node));
node[1] = 0;
dfs(1);
ans = node[n];
for(int j = 61;j >= 0;j--) {
if(b[j] != 0) {
ans = max(ans, ans ^ b[j]);
}
}
printf("%lld\n", ans);
return 0;
}
[SCOI2016]幸运数字
此题只需使用一个新操作：合并两个线性基。
因为两个线性基的长度都不超过 $\log a$，那就直接暴力合并。
时间复杂度 $O(\log^2 a)$。
然后用倍增即能得到 $O(n\log n\log^2 a)$ 的优秀做法，不过题解还有更优秀的，但不是本篇文章的重点。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
const int Inf = 0x3f3f3f3f;
const ll Lnf = 0x3f3f3f3f3f3f3fll;
const int Mod = 1000000007;
const int maxn = 20005;
int n, q, top, head[maxn];
ll a[maxn];
int lg[maxn], dep[maxn], anc[maxn][20];
ll st[maxn][16][65], b[65];
ll ans;
struct Edge {
int v;
int next;
}Edge[2 * maxn];
void addEdge(int u, int v) {
Edge[++top].v = v;
Edge[top].next = head[u];
head[u] = top;
}
bool insert(int idx, int idy, ll x) {
for(int j = 61;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue;
if(st[idx][idy][j] != 0) {
x ^= st[idx][idy][j];
}
else {
st[idx][idy][j] = x;
return true;
}
}
return false;
}
void merge(int idx1, int idy1, int idx2, int idy2, int idx3, int idy3) {
for(int j = 61;j >= 0;j--) {
st[idx3][idy3][j] = st[idx1][idy1][j];
}
for(int j = 61;j >= 0;j--) {
if(st[idx2][idy2][j] != 0) {
insert(idx3, idy3, st[idx2][idy2][j]);
}
}
}
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
anc[u][0] = fa;
insert(u, 0, a[u]);
insert(u, 0, a[fa]);
for(int k = 1;(1 << k) <= dep[u];k++) {
anc[u][k] = anc[anc[u][k - 1]][k - 1];
merge(u, k - 1, anc[u][k - 1], k - 1, u, k);
}
for(int i = head[u];i;i = Edge[i].next) {
int v = Edge[i].v;
if(v == fa) continue;
dfs(v, u);
}
}
bool insertb(ll x) {
for(int j = 61;j >= 0;j--) {
if(((1ll << j) & x) == 0) continue;
if(b[j] != 0) {
x ^= b[j];
}
else {
b[j] = x;
return true;
}
}
return false;
}
void mergeb(int idx, int idy) {
for(int j = 61;j >= 0;j--) {
if(st[idx][idy][j] != 0) {
insertb(st[idx][idy][j]);
}
}
}
void LCA(int x, int y) {
if(dep[x] < dep[y]) {
swap(x, y);
}
while(dep[x] > dep[y]) {
int k = lg[dep[x] - dep[y]];
mergeb(x, k), x = anc[x][k];
}
if(x == y) {
return;
}
for(int k = lg[dep[x]];k >= 0;k--) {
if(anc[x][k] != anc[y][k]) {
mergeb(x, k), x = anc[x][k];
mergeb(y, k), y = anc[y][k];
}
}
mergeb(x, 0);
mergeb(y, 0);
}
int main() {
scanf("%d%d", &n, &q);
lg[0] = -1;
for(int i = 1;i <= n;i++) {
lg[i] = lg[i / 2] + 1;
}
for(int i = 1;i <= n;i++) {
scanf("%lld", &a[i]);
}
for(int i = 1;i <= n - 1;i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs(1, 0);
while(q--) {
int x, y;
scanf("%d%d", &x, &y);
if(x == y) {
printf("%lld\n", a[x]);
continue;
}
memset(b, 0, sizeof(b));
LCA(x, y);
ans = 0;
for(int j = 61;j >= 0;j--) {
if(b[j] != 0) {
ans = max(ans, ans ^ b[j]);
}
}
printf("%lld\n", ans);
}
return 0;
}
总结
作为省选中相对简单的算法，线性基代码实现难度很低，在省选中相对于其它题目一般都为送分题，但线性基背后的性质和应用是我们在比赛中所应注意的，能够快速的推出题干中线性基的相关条件，就如 [WC2011]最大XOR和路径，分析出不用得到所有的环而是只用标记法得出的环就可组成的线性基是解题的关键，或许在场上不能证明的结论，但希望仍能有机会在场上实现出来，所以场下的经验积累就十分重要。
就这样吧，跑路了，如果还有很好的题会继续更新的。