线性基

发表于 | 分类于

线性基

定义

张成

设 $T⊆S$，所有这样的子集 $T$ 的异或和的集合称为集合 S $ S $的张成，记作 $ span(S)$。

线性相关

对于集合$S$，如果存在一个元素$S_i$，使得$S$去除这个元素之后得到的集合 $S’$的张成$span(S’)$ 中包含$S_i$则称这个集合线性相关。

也就是说包含一个元素可以由其他元素异或得到。

一个显然的结论是，对于这个线性相关的集合 $S$，去除这个元素后，集合的张成不变。

线性基

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

$S⊆span(B)$，即$ S $是$ B $的张成的子集；
$ B $是线性无关的。
集合$ B $中元素的个数，称为线性基的长度。

性质

基本性质

  • $ B $是极小的满足线性基性质的集合，它的任何真子集都不可能是线性基；

  • $ S $ 中的任意元素都可以唯一表示为$ B $中若干个元素异或起来的结果。

构造

集合$S$中最大的数二进制意义下有$L$位，那么$a[0,…，L]$这个数组来储存线性基

这种构造方法构造的线性基有一个特殊的性质：

对于任意的$i,a_i$，仅有如下两种情况：

1.$a_i=0$且

  • 当且仅当对于$j>i$的$a_i$的第$i$个二进制位可能为$1$

2.$a_i≠0$且

  • 整个$a$数组中只有$a_i$的第$i$个二进制位为1
  • $a_i$更高的二进制位一定为0
  • $a_i$更低的二进制位可能为1

    具体构造方法

    首先，线性基是动态构造的，我们只需要从空的$ a $开始，每次考虑在一个已存在的线性基中插入一个数$ t $即可。

每次插入的时候，从$ t $的最高位的$1$开始考虑，如果这一位存在于线性基当中那么我们需要将$t$的这一位消掉，于是我们可以异或上线性基的这一位，然后继续插入。

如果不存在，那么我们可以将$t$插入到线性基当前位置上。但是要注意满足上面的性质，见具体流程。

流程

逆序枚举$t$所有为$1$的二进制位，$i=for(L->0)$对于每个$i$

  • 如果$a_i≠0$,则
t=t^a[i]
  • 如果$a_i=0$,则
1
2
3
4
5
6
7
8
for(k=0...i)
 	if(t&(1<<k))
    		t=t^a[i];
   for(k=i+1...L)
   	if(a[k]&(1<<j))
     	a[k]=a[k]^t;
   a[j]=t;
   return;

子集最大异或和

就是线性基的异或和么

code:

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
const int MAXL = 60;
   
   long long a[MAXL + 1];
   void insert(long long t)
   {
       for (int j = MAXL; j >= 0; j--)
       {
           if (!(t & (1ll << j))) continue;
           if (a[j]) t ^= a[j];
           else
           {
               for(int k=0;k<j;k++) 
                   if(t&(1ll<<k)) 
                       t^=a[k];
               for(int k=j+1;k<=MAXL;k++) 
                   if(a[k]&(1ll<<j))
                       a[k]^=t;
               a[j]=t;
               return;
           }
       }
   }
   long long queryMax()
   {
       long long ret=0;
       for(int i=0;i<=MAXL;i++) 
       	res^=a[i];
       return res;
   }

子集K小异或和

首先根据我们构造的线性基，显然可以知道，最高位的$1$异或上肯定最大，之后的$1$再异或也会变大因为如果跟之前高位的$1$有重复就不满足之前的性质，也就是插入的时候如果当前位有的话，会异或上然后消掉。于是第K大就是K的二进制分解来选取线性基中的元素。

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//这里用一个vector <int> v保存了线性基，因为可以动态插入快速查询大小。
   long long query(long long k) 
   {
           if (int(v.size()) != n)
           {
               k--;
           }
           if (k > (1ll << v.size()) - 1) 
           	return -1;
           long long ans = 0;
           for (size_t i = 0; i < v.size(); i++) 
           {
               if (k & (1ll << i))
               {
                   ans ^= v[i];
               }
           }
           return ans;
}

后续例题见博客更新