在处理异或问题时经常用到线性基,比如一个序列中某几个数的异或第k大(小)值,判断某个数能否通过序列中的数字异或出来等。
定义 / Defination
在线性代数中,对于向量组 α1,α2,…,αn ,我们把其张成空间的一组线性无关的基成为该向量组的线性基。
而在我们学习算法的语境下,线性基是一个数的集合,并且每个序列都拥有至少一个线性基,取线性基中若干个数异或起来可以得到原序列中的任何一个数。
线性基三大性质
- 原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
- 线性基里面的任意一些数异或起来都不能得到0。
- 线性基里面的数的个数唯一,并且在保持性质一的前提下,数的个数是最少的。
线性基的构造方法
设数组p为a的线性基数组,下标从0开始,大约63个就够了。这里是将数字x进行二进制分解再插入到线性基数组中。注意要从大到小遍历,贪心的思想。
只需要这样写就可以了:
void ins(int x) { for(int i = MAXL; i >= 0; -- i)//从大到小! { if(!x)return; if(!(x >> i & 1))continue; if(p[i])x ^= p[i]; else { p[i] = x; break; } } }
这样构造的线性基并不完美,还需要进行一次重构,使得这个线性基更好。
重构 / Rebuild
void rebuild() { tot = 0; for(int i = 0;i <= MAXL; ++ i) { for(int j = i - 1;j >= 0; -- j) if(p[i] >> j & 1)p[i] ^= p[j]; if(p[i])d[tot ++] = p[i]; } }
求最大异或和
对于重构后的线性基,只需要将所有向量(数字)异或起来即可。
int que_max() { int res = 0; for(int i = 0;i < tot; ++ i)res ^= d[i]; return res; }
求第k小异或和
如果要求第k大,就是求第(1 << tot) - k + 1小的异或和。注意要判断是否可以组合出0,举个例子,求最大异或和可以这么写:cout << que_min((1LL << tot) - (tot == N)) << endl;
int que_min(int k) { if(tot != N)-- k; if(k >= (1LL << tot))return -1; int res = 0; for(int i = 0;i < tot; ++ i)if(k >> i & 1)res ^= d[i]; return res; } cout << que_min((1LL << tot) - (tot == N)) << endl;
Comments NOTHING