线性基小结

线性基是常用来解决子集异或/线性空间中一些题目的算法

算法

具体定义概念见Menci的博客,写的很好,这里只记录一些感性的理解

注:以下没有注明的话,线性基均指的是异或线性基

简介

简单来说,线性基就是在异或运算下,只需要一个大小为cc的集合β\betacc表示数字位数)就能通过相互进行异或运算表示出一个全集SS中的所有数。也就是说,它可以将集合SS在异或意义下的一个压缩

为什么只需要大小为cc的集合呢?显然,只需要一个全是2的幂次的集合就能表示出所有数,因此上界肯定是cc

它可以表示成这样一组数(也可以说是一组0/10/1向量):,其中axa_x的最高位的11在第xx

而在这里所提到的线性基(包括代码实现)都是最简意义下的。即只要某一位它出现在了某个数的最高位,那么其他数字中它这一位就为00(如果不为00就可以消掉);而如果某一位没有作为最高位出现过,可以有多个数字这一位为00

由此不难看出,它是一个类似于对角矩阵的东西,大概可能长这样:

[1010000011001000000000001000000011000000000000001]\begin{bmatrix} 1&0&1&0&\cdots&0&0&0\\ 0&1&1&0&\cdots&0&1&0\\ 0&0&0&0&\cdots&0&0&0\\ 0&0&0&1&\cdots&0&0&0\\ 0&0&0&0&\cdots&1&1&0\\ 0&0&0&0&\cdots&0&0&0\\ 0&0&0&0&\cdots&0&0&1 \end{bmatrix}

其中第ii行表示线性基中的aia_i

实现

显然,我们可以用O(nc2)O(nc^2)的高斯消元暴力求线性基,但是这样并不优美。于是有一种O(nc)O(nc)贪心动态构造的方法:

对于一个新加入的数xx,从大到小枚举xx的每一个为11的二进制位ii

  • 如果ai=0a_i=0,那么令ai=xa_i = x

    用已经存在的aj(j<i)a_{j(j<i)}消掉xx在第jj位的影响

    用当前的xx消掉已经存在的aj(j>i)a_{j(j>i)}在第ii位的影响

    并结束插入的过程

  • 否则x=xaix = x \oplus a_i

这样贪心的构造显然是对的,证明见文章开头的博客,这里不多赘述

写一下感性理解,对于当前为11的最高位ii,如果ai0a_i\ne0,就说明已经存在一个最高位为ii的数,那么直接用这个aia_i就能把xx的第ii位消掉;而如果ai=0a_i=0,就说明此时的xx是最先出现的最高位为ii的数,直接插进线性基即可

合并

扫一遍线性基,暴力插入另一个即可

复杂度O(c2)O(c^2)

具体见此

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
namespace Basis
{
const int Maxlen = 30;

int A[Maxlen + 10];

inline int insert (int x)
{
for (int i = Maxlen; ~i; --i)
{
if (!(x & (1 << i))) continue;
if (!A[i])
{
for (int j = 0; j < i; ++j) if (x & (1 << j)) x ^= A[j];
for (int j = i + 1; j <= Maxlen; ++j) if (A[j] & (1 << i)) A[j] ^= x;
A[i] = x;
return 1;
}
x ^= A[i];
}
return 0;
}
}

应用

求异或最大/小值;与xx异或的最大/小值

高位往低位贪心,如果异或上当前的数能使答案更优就异或

求异或kk小值

由于线性基中从高位往低位的前缀异或和显然是单调不降的,因此只需要对kk做二进制拆分,取线性基中对应位数的值异或起来即可

核心代码:

1
2
for (int i = 0; i <= Maxlen; ++i) if (A[i]) v.push_back(A[i]);
for (int i = 0; i < v.size(); ++i) if (k & (1ll << i)) ans ^= v[i];

求异或排名

与上个操作是互逆操作

核心代码:

1
2
for (int i = 0; i <= Maxlen; ++i) if (A[i]) bit.push_back(i);
for (int i = 0; i < bit.size(); ++i) if (x & (1ll << bit[i])) ans |= (1 << i);

解异或方程组

「SDOI2010」外星千足虫

扩展到线性空间

线性基也可以用来求解线性空间的解方程/线性无关问题

具体可见「JLOI2015」装备购买 ,但是我并没有写博客,就把代码放这里:

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
namespace Basis
{
long double A[Maxn][Maxn];
int Vis[Maxn];

inline int insert (long double x[])
{
for (int i = 1; i <= N; ++i)
{
if (fabs(x[i]) < eps) continue;

if (!Vis[i])
{
long double base = x[i];
for (int j = i; j <= N; ++j) x[j] /= base;

for (int j = i + 1; j <= N; ++j)
{
if (!Vis[j]) continue;
base = x[j];
for (int k = 1; k <= N; ++k) x[k] -= base * A[j][k];
}

for (int j = 1; j < i; ++j)
{
if (!Vis[j]) continue;
base = A[j][i];
for (int k = 1; k <= N; ++k) A[j][k] -= base * x[k];
}

for (int j = 1; j <= N; ++j) A[i][j] = x[j];
Vis[i] = 1;
return 1;
}

long double base = x[i];
for (int j = i; j <= N; ++j) x[j] -= base * A[i][j];
}
return 0;
}
}

最大路径异或和

「WC2011」Xor - 线性基

树上路径最大异或和

「WC2011」Xor


其他应用基本都是建立在这些操作之上了

感谢你的赞赏!