跳转至

异或空间线性基

向量空间的基是这个向量空间的特殊子集，基的元素称为基向量，基向量相互之间线性无关。向量空间的任何元素都能唯一地用基向量的线性组合来表示。一个向量空间的基可以有很多，但是每个基的基向量个数相同（最小数量）。

每一个整数都可以被表示为一个二进制数，也就等价于一个异或空间的向量。线性基可以帮助我们求出一个数集的子集最大异或和或者子集 \(k\) 大异或和，以及最大权线性无关子集等。

线性基的构造

构造线性基的核心是：对于异或空间向量集合 \(S\)，任取其中两个元素 \(x,y\)，\(S\) 和 \(S/\{x\}\cup \{x\oplus y\}\) 在向量空间等价。

线性基是动态构造的，即遍历集合中的每一个元素，将它们依次插入。假设已知当前集合的线性基，考虑添加一个元素 \(x\)。记当前线性基中最高位为第 \(i\) 位的基向量为 \(bs[i]\)，不存在则为 \(0\)。我们从高到低依次遍历每一个 \(bs[i]\)，执行以下步骤：

  • 如果 \(x\) 的最高位为 \(i\)：
  • 如果 \(bs[i]\) 存在，则 \(x\leftarrow x\oplus bs[i]\)；
  • 否则：
    • 枚举 \(bs[1,i-1]\)，尽可能消掉 \(x\) 的较低位；
    • \(bs[i]\leftarrow x\)；
    • 枚举 \(bs[i+1,k]\)，用 \(bs[i]\) 消掉 \(bs[i+1,k]\) 的第 \(i\) 位；
    • 函数返回；
  • 继续遍历 \(i\)；
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
ll bs[LOGV];
void insert(ll x) {
    for(int i = LOGV - 1; i >= 0; i--) {
        if(x & (1ll << i)) {
            if(bs[i] & (1ll << i)) x ^= bs[i];
            else {
                for(int j = i - 1; j >= 0; j--) {
                    if(x & (1 << j)) x ^= bs[j];
                }
                bs[i] = x;
                for(int j = i + 1; j < LOGV; j++) {
                    if(bs[j] & (1 << i)) bs[j] ^= x;
                }
                break;
            }
        }
    }
}

本段代码具有和高斯消元相同的效果，即得到的是一个行最简形矩阵。

如果值域是 long long 范围，则依靠位运算可以达到单次 insert \(O(\log V)\) 的时间复杂度。若值域较大，则使用 bitset 仍可以达到 \(O(\frac{\log^2 V}{\omega})\) 的复杂度。

例题

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
#include<iostream>
#define ll long long
using namespace std;
const int LOGN = 51;

int n;

ll bs[LOGN];
void insert(ll x) {
    for(int i = LOGN - 1; i >= 0; i--) {
        if(x & (1ll << i)) {
            if(bs[i]) x ^= bs[i];
            else {
                for(int j = i - 1; j >= 0; j--) {
                    if(x & (1ll << j)) x ^= bs[j];
                }
                bs[i] = x;
                for(int j = i + 1; j < LOGN; j++) {
                    if(bs[j] & (1ll << i)) bs[j] ^= x;
                }
                return;
            }
        }
    }
}

int main() {

    cin >> n;
    while(n--) {
        ll x;
        cin >> x;
        insert(x);
    }

    ll ans = 0;
    for(int i = 0; i < LOGN; i++) ans ^= bs[i];
    cout << ans << endl;

    return 0;
}

P4151 [WC2011] 最大XOR和路径

题意

给定一个无向连通图 \(G=(V,E)\)，边有边权。求一条 \(1\rightarrow n\) 的路径（不要求为简单路径），使得路径上所有边的边权异或和最大，输出最大值。

\(n\le 5\times 10^4,\ m\le 10^5\)

考虑图的一棵生成树 \(T\)。对于每一条非树边 \(e\in E/T\)，都能和树边形成一个 环，称为基本环。一个基本环的权值定义为环上所有边的边权异或和。

定理 1：对于图上任意一个环 \(C\)，都存在一个基本环的集合 \(B\)，使得 \(C\) 的边权异或和等于 \(B\) 的权值异或和。

定理 2：对于任意一个基本环的集合 \(B\)，都存在图上的一个环 \(C\)，使得 \(B\) 的权值异或和等于 \(C\) 的边权异或和。

注意连通性

对于不连通的图，显然不存在生成树 \(T\)。因此我们都默认图是连通的。如果图不连通，我们分开考虑各个连通块即可。

证明

记 \(s[u]\) 表示 \(T\) 上 \(1\rightarrow u\) 的路径的异或和。显然，对于非树边 \(e=(u,v,w)\)，其形成的基本环的权值为 \(s[u]\oplus s[v]\oplus w\)。

对于定理 1，考虑构造。我们选取 \(C\) 中的所有非树边 \(e_i\) 对应的基本环。对于树边，我们也将它们假想为一条非树边，容易发现它们对应的“基本环”的权值等于 \(0\)。\(C\) 中的每个节点的返根链都被计算了偶数次，\(C\) 中的每条边都被计算了奇数次，权值相等。

对于定理 \(2\)，仍然考虑构造。由于图是连通的，我们可以构造一棵包含 \(|B|-1\) 条路径的“生成树”将所有环连接起来。我们从“生成树”的根节点出发，依次遍历每个环，并在环的遍历结束后回到“生成树”上，继续遍历。最终回到出发点，生成树上的每条边都被经过了偶数次，每个基本环都被经过了一次，且最终的路径是一个闭合的环。

由于题目要求一条路径，而不是一个环。显然，任意两条 \(1\rightarrow n\) 的路径的异或都是环，并且路径和任意环的异或仍然是一条异或路径。

因此我们先随便选一条 \(1\rightarrow n\) 的路径，权值记为 \(x\)。然后找出所有基本环，记它们组成的集合为 \(B\)。然后使用线性基求出 \(\max_{B_1\subseteq B}\{x\oplus\left(\bigoplus_{e\in B_1}w(e) \right)\}\) 即可。

代码 
 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
#include<iostream>
#include<cstring>
#include<bitset>
#define ll long long
using namespace std;
const int N = 5e4 + 10;
const int M = 1e5 + 10;
const int LOGV = 63;

struct Edge {
    int v;
    ll w;
    int next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v, ll w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, m;
ll s[N];

ll bs[LOGV];
void insert(ll x) {
    for(int i = LOGV - 1; i >= 0; i--) {
        if(x & (1ll << i)) {
            if(bs[i] & (1ll << i)) x ^= bs[i];
            else {
                for(int j = i - 1; j >= 0; j--) {
                    if(x & (1 << j)) x ^= bs[j];
                }
                bs[i] = x;
                for(int j = i + 1; j < LOGV; j++) {
                    if(bs[j] & (1 << i)) bs[j] ^= x;
                }
                break;
            }
        }
    }
}

void dfs(int u, int ef) {
    for(int i = head[u]; i; i = pool[i].next) {
        if(i == ef) continue;
        int v = pool[i].v;
        ll w = pool[i].w;
        if(~s[v]) {
            insert(s[u] ^ s[v] ^ w);
        } else {
            s[v] = s[u] ^ w;
            dfs(v, i ^ 1);
        }
    }
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    memset(s, -1, sizeof(s));
    s[1] = 0;
    dfs(1, 0);

    ll ans = s[n];
    for(int i = LOGV - 1; i >= 0; i--) {
        if(!(ans & (1ll << i))) ans ^= bs[i];
    }

    cout << ans << endl;

    return 0;
}

P3733 [HAOI2017] 八纵八横

请见线段树分治