线性基学习笔记

线性基学习笔记

什么是线性基?

基在数学中指用于刻画向量空间的一组向量,该空间内的所有向量都可以通过基来表示。

oi中的线性基常在异或运算中出现。含义为可以表示$n$个数的异或运算结果的若干个数。

设存在$n$个数$a_1,a_2,a_3…a_n$。取出若干个数进行异或操作,最多有$2^n$种结果。

这$n​$个数的线性基为$k​$个数$b_1,b_2,b_3…b_k​$。取出若干个数进行异或操作,其所得结果与前面相同。

当$k$取最小值时,这$k​$个数被称为原数的线性基。

构造线性基

依次扫描原来的$n​$个数,再将每个数按照2进制位从高位向低位扫描。

若当前位为1:

  • 如果$b[当前位数]=0$,将$b[当前位数]$放为当前的数,结束循环
  • 如果$b[当前位数]\ne0​$,将当前的数^$b[当前位数]​$,继续循环

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=1;i<=n;++i)
{
for(int j=50;j>=0;--j)
if(a[i]&(1ll<<j))
{
if(!b[j])
{
b[j]=a[i];
break;
}
a[i]^=b[j];
}
}

常见用法

求最大值

从高位到低位扫描线性基,如果异或线性基可以石当前答案变大,则异或。

代码实现:

1
2
for(int i=50;i>=0;--i)
ans=std::max(ans,ans^b[i]);

判断可行

判断一个数是否可以通过异或操作获得。

从高位到低位扫描,如果当前位为$1​$:

  • 存在线性基,则与线性基异或
  • 不存在线性基,则不可获得

如果在扫描过程中,该数变成$0$,则可获得。

记得根据题意在构造过程中特判$0$。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void check(int x)
{
for(int i=50;i>=0;--i)
if((x>>i)&1)
{
if(bs[i])
x^=bs[i];
else
{
puts("NO");
return;
}
}
puts("YES");
}

构造异或值域

线性基有$k$个数,那么异或的结果有$2^k$个。

而原始的 $ n $ 个数的异或结果有 $ 2^n $ 个。那么,每种异或结果有 $2^{n-k}$ 种获得方式。

例题:luogu4869

求第k小的异或结果

首先将我们的线性基改造得更加优美。我们要将每一个线性基化到最小来求得k小值。

从高到低位扫描线性基,对于线性基的每一位(不包括最高位),如果为$1$,则与其线性基异或。

将所有线性基排序,二进制拆分$k​$,如果第$x​$位上为$1​$,则将$ans​$^第$x​$大的线性基。

例题:loj114

区间异或和最大

按照区间右端点递增的顺序离线处理询问。

在构造线性基的同时贪心选择靠右的数。

处理每一个询问时,如果线性基的位置$\geq​$区间左端点且使答案更优,则异或。

例题:cf1100f