线性基（Linear Basis）学习笔记

• 2022 年 1 月 5 日
• 筆記

前言

我看网络上没有什么非常系统的教学，可能是我太菜了吧，现在才学，做个记录给自己看。

简略介绍

一个数集能两两异或，能表出许多新的数。

线性基是一个集合，能够在记录最少的数的基础上，表示出一个等价的异或集合。+

常用来解决最大异或子集问题。

下文假设 \(L\) 为值域最大值在二进制下的位数。

构造方法 & 解决问题

插入

bool insert(ll val) {
	fd(i, L, 0)
		if (val >> i & 1)) {
			if (!b[i]) { // b[i] 是记录线性基的数组
				b[i] = val;
				break;
			}
			val ^= b[i];
		}
	return val;
}

如果说 \(\text{val}\) 能被表出，那么它一定会在最后变成 \(0\) 。否则，我们认定下标 \(i\) 的位置放置的数的二进制下第 \(i\) 位一定是 \(1\)。并将它插入。

不难发现，一个插入的数被填进第 \(i\) 位时，其更高位一定被全部异或 \(0\) ，故 \(i\) 是它的最高位 \(1\) 的位置。记住这个性质，会在下面使用。

插入一个数复杂度是 \(O(L)\) 的。

最大异或子集

根据上面的性质，我们从高位贪心地考虑，希望能够尽量让高位的 \(1\) 能够出现。

ll mx() {
    ll ret=0;
    fd(i, L, 0)
        if((ret ^ b[i]) > ret)
            ret ^= b[i];
    return ret;
}

\(O(L)\)。

合并两个线性基

直接把一个线性基中的元素插入另一个，\(O(L^2)\) 。

求第 \(k\) 小能被表出元素

我们改造这个线性基，使得每一位相互独立。类似高斯消元。从低位到高位消。

void rebuild() {
	fo(i, 1, L)
		fo(j, 1, i)
			if(d[i] >> (j - 1) & 1)
                d[i] ^= d[j - 1];
}
ll k_th(ll k) {
    // 如果算上零的话需要有特判
	if(k == 1 && tot < n)	return 0;//特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0，tot表示线性基中的元素个数，n表示序列长度
	if(tot < n)	--k;//类似上面，去掉0的情况，因为线性基中只能异或出不为0的解
	// 记得先 rebuild
	ll ret = 0;
	fo(i, 1, L)
        if(d[i]) {
            if(k & 1)	ret ^= d[i];
            k >>= 1;
        }
   	return ret;
}

顺便一提，实际上 \(\text{rebuild}\) 之后的线性基是完全等价的，可以正常做其他操作。

删除

在线的做法太复杂了一般不考不是很优美，直接说离线吧。

在线性基的每一个位置维护一个最晚插入时间 \(t\) ，那么插入的时候

FOR i=L~0
如果 目前这一位线性基为空
则将目前这一位的线性基附为 (v1,t1)
否则：
将目前这一位的线性基记为 (v2,t2)
      如果 t2<t1：
          将目前这一位的线性基替换为 (v1,t1)
          v2^=v1
          用(v2,t2)插入下一位线性基
      否则：
          v1^=v2
          用(v1,t1)插入下一位线性基

在查询的时候只需要看 \(t \ge t_0\) 的位置就好了。