线性基学习笔记

概念

定义：给定数集 \(S\)，以异或运算张成的数集与 \(S\) 相同的极大线性无关集，称为原数集的一个线性基。
简单地说，线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原序列中的任何一个数。
性质

• 性质一
  

• 取线性基中若干个数异或起来可以得到原序列中的任何一个数。
  

• 性质二
  

• 线性基中任意选择若干个数异或
  

• 性质三
  

• 线性基内部的数个数唯一，且在保持性质一的前提下，数的个数是最少的。
  

证明

性质二

若 \(d_i\oplus d_j\oplus d_k = 0\)，那么 \(d_i\oplus d_j = d_k\)。由于 \(d_k\) 可以被得到，那么 \(d_k\) 不可能加入线性基。
性质一

分类讨论插入的数 \(x\)：
若不能插入线性基，显然就是在线性基中有几个数和它异或之后变成了零，那么也就是说线性基中若干个数异或后可以为 \(x\)，
若可以插入，设插入到了第 \(i\) 位。那么 \(x\oplus d[a]\oplus d\oplus d[c]\oplus\dots\oplus d[k]=d\)。
则 \(d\oplus d[a]\oplus d\oplus d[c]\oplus\dots\oplus d[k]=x\)。
所以 \(x\) 也可以由线性基中若干个数异或得到。
性质三

如果原集合中每个数都被插入进了线性基，则显然成立，如果插入顺序是 \(a,b,c,x,\dots\) 且 \(x\) 没有被成功插入，就是 \(a\oplus b\oplus c=x\)。
那么无论怎么改变顺序也一定有一个数插不进去。所以个数是一定的。
若去掉线性基里面的任何一个数，都会使得原序列里的数无法用线性基里的数异或得到，所以没有多余的元素。
所以线性基的元素个数在保持性质一的前提下，一定是最少的。
基操

插入

将 \(x\) 转为二进制，从它的高位开始，如果当前位为 \(1\)，并且线性基 \(p\) 的第 \(i\) 位上没有数，那就赋成当前值 \(x\)。否则，将 \(x\) 异或 \(p_i\)。
则样子能保证 \(x\) 能通过异或的那几个数得到。

1. void insert(int k) {
2.         for(int i=60;i>=0;i--) {
3.                 if(!(k&(1LL<<i))) continue;
4.                 if(!p[i]){
5.                         p[i]=k;
6.                         break;
7.                 }
8.                 k^=p[i];
9.         }
10. }

复制代码

\(k\) 小值

不想说明。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！