概念
定义：给定数集 (S)，以异或运算张成的数集与 (S) 相同的极大线性无关集，称为原数集的一个线性基。
简单地说，线性基是一个数的集合。每个序列都拥有至少一个线性基。取线性基中若干个数异或起来可以得到原序列中的任何一个数。
性质
- 性质一
- 取线性基中若干个数异或起来可以得到原序列中的任何一个数。
- 性质二
- 线性基中任意选择若干个数异或
- 性质三
- 线性基内部的数个数唯一，且在保持性质一的前提下，数的个数是最少的。
证明
性质二
若 (d_ioplus d_joplus d_k = 0)，那么 (d_ioplus d_j = d_k)。由于 (d_k) 可以被得到，那么 (d_k) 不可能加入线性基。
性质一
分类讨论插入的数 (x)：
若不能插入线性基，显然就是在线性基中有几个数和它异或之后变成了零，那么也就是说线性基中若干个数异或后可以为 (x)，
若可以插入，设插入到了第 (i) 位。那么 (xoplus d[a]oplus d[b]oplus d[c]oplusdotsoplus d[k]=d[i])。
则 (d[i]oplus d[a]oplus d[b]oplus d[c]oplusdotsoplus d[k]=x)。
所以 (x) 也可以由线性基中若干个数异或得到。
性质三
如果原集合中每个数都被插入进了线性基，则显然成立，如果插入顺序是 (a,b,c,x,dots) 且 (x) 没有被成功插入，就是 (aoplus boplus c=x)。
那么无论怎么改变顺序也一定有一个数插不进去。所以个数是一定的。
若去掉线性基里面的任何一个数，都会使得原序列里的数无法用线性基里的数异或得到，所以没有多余的元素。
所以线性基的元素个数在保持性质一的前提下，一定是最少的。
基操
插入
将 (x) 转为二进制，从它的高位开始，如果当前位为 (1)，并且线性基 (p) 的第 (i) 位上没有数，那就赋成当前值 (x)。否则，将 (x) 异或 (p_i)。
则样子能保证 (x) 能通过异或的那几个数得到。
void insert(int k) {
for(int i=60;i>=0;i--) {
if(!(k&(1LL<<i))) continue;
if(!p[i]){
p[i]=k;
break;
}
k^=p[i];
}
}
最大值
接着采取贪心的思想，从线性基的最高位开始，若当前的答案异或线性基的这个元素可以变得更大，那么就异或它。因为线性基的 (p_i) 的最高位一定为 (i)。
int maxXor(){
int res=0;
for(int i=60;i>=0;i--) res=max(res,(res^p[i]));
return res;
}
最小值
同样是贪心，最大值要看情况。
for(int i=60;i>=0;i--) ans=min(ans^p[i],ans);
(k) 小值
不想说明。
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
