线性基学习笔记

#前置知识

#异或和

集合 $S$ 的异或和为 $\text{xor}_{i = 1}^{|S|} S_i$（即 $S_1 \text{ xor } S_2 \text{ xor } \dots \text{ xor } S_{|S|}$）。

#张成

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

#线性相关与线性无关

对于一个集合 $S$，如果存在一个元素 $S_i$ 使得 $S$ 在去除这个元素后得到的集合 $S'$ 满足 $S_i \in \text{span}(S')$，即存在一个元素 $S_i$ 可以通过集合中的若干个剩余元素异或得到，则称集合 $S$ 线性相关。

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

#线性基

#定义

我们称集合 $B$ 是集合 $S$ 的线性基，当且仅当：

1. $S \subseteq \text{span}(B)$；
2. $B$ 是线性无关的。

集合 $B$ 中元素的个数称为线性基的 长度。

线性基有以下几个性质：

1. $S$ 中的任意元素都可以 唯一 表示为 $B$ 中若干个元素的异或和（对应条件 1）；
2. $B$ 是极小的满足线性基性质的集合，它的任何真子集都不可能是线性基（对应条件 2）；
3. $B$ 中没有异或和为 $0$ 的子集（对应条件 2）；
4. $B$ 中每个元素的二进制最高位互不相同；
5. 在 $B$ 中选取若干个元素异或起来得到一个元素，用这个元素去替换 $B$ 中的任意一个元素，得到的新集合 $B'$ 张成的空间不变。

#构造

#代码

1
2
3
4
5
6
7
8
9
10
11
12

inline void insert(unsigned long long x) {
    for (int i = 50; ~i; i--) {
        if ((x >> i) & 1) {
            if (a[i]) {
                x ^= a[i];
            } else {
                a[i] = x;
                return;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

inline void insert(unsigned long long x) {
    for (int i = 50; ~i; i--) {
        if ((x >> i) & 1) {
            if (a[i]) {
                x ^= a[i];
            } else {
                for (int k = 0; k < i; k++) {
                    if (x & (1ull << k)) x ^= a[k];
                }

                for (int k = i + 1; k <= 50; k++) {
                    if (a[k] & (1ull << i)) a[k] ^= x;
                }

                a[i] = x;
                return;
            }
        }
    }
}

#应用

#检查某个数是否能被表示成集合中若干元素的异或和

首先构造出这个集合的线性基，然后检测这个数是否能被插入到线性基中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

inline bool check(unsigned long long x) {
    for (int i = 50; ~i; i--) {
        if ((x >> i) & 1) {
            if (a[i]) {
                x ^= a[i];
            } else {
                // 能被插入表示集合的张成中不包括 x
                return false;
            }
        }
    }

    return true;
}

#求最大子集异或和

从高位到低位考虑基，若异或后变大，则异或。

由于 $a_{0 \sim i - 1}$ 都不含 $i$ 及以上的位，其最大贡献仅为 $2^i - 1$。有两种情况：

1. 若此时 $\it{ans}$ 的第 $i$ 位是 $0$，则异或上 $a_i$ 至少带来 $2^i$ 的收益，大于后面可能的所有收益。同时，(ans ^ a[i]) > ans 也必然成立。
2. 若此时 $\it{ans}$ 的第 $i$ 位是 $1$，至少在这一位有 $2^i$ 的亏损，大于后面的位可能的所有收益。同时，(ans ^ a[i]) > ans 也必不成立。

1
2
3

for (int i = 50; ~i; i++) {
    if ((ans ^ a[i]) > ans) ans ^= a[i];
}

1
2
3

for (int i = 0; i <= 50; i++) {
    ans ^= a[i];
}

#合并线性基

暴力插入即可。

1
2
3
4
5
6
7

inline void insert(unsigned long long *a, unsigned long long x);

void merge(unsigned long long *a, unsigned long long *b) {
    for (int i = 0; i <= 50; i++) {
        insert(a, b[i]);
    }
}

#第 k 小子集异或和

先将按照上文中的「方法 2」建立对角线性基。

将 $k$ 二进制拆分，每一位的 $0$ / $1$ 对应异或时选 / 不选线性基存在的这一位。

证明：线性基中存在的位的 $0$ / $1$ 唯一确定了一个异或出的数，由于每个位只在一个基中为 $1$，这些位组成的二进制数的大小就可以代表异或出的数的大小。

题目：LibreOJ #114. k 大异或和

预处理出线性基中所有存在的位：

1
2
3

for (int i = 0; i <= 50; i++) {
    if (a[i]) p[cnt++] = a[i];
}

对于每次询问 $k$：

1
2
3
4
5
6
7
8
9
10
11
12
13

if (cnt != n) k--;  // 确保选择的是非空子集

if (k >= (1ull << cnt)) {  // 不同的异或和数量不足 k
    cout << -1 << endl;
} else {
    ans = 0;

    for (int i = 0; i < cnt; i++) {
        if (k & (1ull << i)) ans ^= p[i];
    }

    cout << ans << endl;
}

#参考资料

1. 线性基学习笔记，游宇凡，2019 年 6 月 12 日。
2. 线性基学习笔记，黄浩睿，2017 年 2 月 25 日。
3. 线性基小记，command-block，2020 年 10 月 21 日。
4. 线性基，OI Wiki，2021 年 3 月 13 日。