Skip to content

线性基学习笔记

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

线性基在竞赛中常用来解决子集异或类题目。

如无特殊说明,本文中所述的集合均为无符号整数集。

前置知识

异或和

集合 SS 的异或和为 xori=1SSi\text{xor}_{i = 1}^{|S|} S_i(即 S1 xor S2 xor xor SSS_1 \text{ xor } S_2 \text{ xor } \dots \text{ xor } S_{|S|})。

张成

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

线性相关与线性无关

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

相对地,如果不存在这样的元素 SiS_i,则称集合 SS 线性无关

线性基

定义

我们称集合 BB 是集合 SS 的线性基,当且仅当:

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

集合 BB 中元素的个数称为线性基的 长度

线性基有以下几个性质:

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

构造

对集合 SS 的每个数 xx 转为二进制,自高位向低位扫描,若 xx 的第 kk 位为 11,如果 aka_k 不存在,那么令 ak=xa_k = x 并结束扫描,如果存在则令 x=x xor akx = x \text{ xor } a_k

在 Menci 的《线性基学习笔记》中还给出了另一种线性基的构造方法,这种方法将原本的三角基消为了对角基:

设集合 SS 中最大的数在二进制意义下有 LL 位,我们使用一个 [0L][0 \ldots L] 的数组 aa 来储存线性基。

  • 逆序枚举 tt 所有为 11 的二进制位 j=L0j = L \rightarrow 0,对于每个 jj
    • 如果 aj0a_j \neq 0,则令 t=txorajt = t \mathbin{\text{xor}} a_j
    • 如果 aj=0a_j = 0,则:
      • 枚举 k[0,j)k \in [0, j),如果 tt 的第 kk 位为 11,则令 t=txorakt = t \mathbin{\text{xor}} a_k
      • 枚举 k(j,L]k \in (j, L],如果 aka_k 的第 jj 位为 11,则令 ak=akxorta_k = a_k \mathbin{\text{xor}} t
      • aj=ta_j = t,结束插入过程。

这种线性基的构造方法保证了一个特殊性质,对于每一个 iiaia_i 有以下两种可能:

  1. ai=0a_i = 0,并且:
    • 只有 满足 j>ij > iaja_j(即,位于 aia_i 后面的所有 aja_j)的第 ii 个二进制位 可能11
  2. ai0a_i \neq 0,并且:
    • 整个 aa 数组中 只有 aia_i 的第 ii 个二进制位为 11
    • aia_i 更高的二进制位(>i> i 的二进制位)一定00
    • aia_i 更低的二进制位(<i< i 的二进制位)可能11

代码

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;
            }
        }
    }
}
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;
            }
        }
    }
}

应用

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

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

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;
}

求最大子集异或和

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

由于 a0i1a_{0 \sim i - 1} 都不含 ii 及以上的位,其最大贡献仅为 2i12^i - 1。有两种情况:

  1. 若此时 ans\it{ans} 的第 ii 位是 00,则异或上 aia_i 至少带来 2i2^i 的收益,大于后面可能的所有收益。同时,(ans ^ a[i]) > ans 也必然成立。
  2. 若此时 ans\it{ans} 的第 ii 位是 11,至少在这一位有 2i2^i 的亏损,大于后面的位可能的所有收益。同时,(ans ^ a[i]) > ans 也必不成立。
for (int i = 50; ~i; i++) {
    if ((ans ^ a[i]) > ans) ans ^= a[i];
}

这种做法由于将三角基消为了对角基,所以第二种情况不会出现。

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

合并线性基

暴力插入即可。

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」建立对角线性基。

kk 二进制拆分,每一位的 00 / 11 对应异或时选 / 不选线性基存在的这一位。

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

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

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

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

对于每次询问 kk

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 日。