前言
本文的线性基指异或线性基。
由于作者太菜了本文的语言不会特别规范。
简介
线性基简称基,它是一个数的集合,并且每个序列都拥有至少一个线性基。
线性基有三个性质:
- 线性基中的几个数异或后不能得到 0。
- 线性基中的数在异或后能得到原序列中的所有数。
- 线性基在保证前两个性质时,会使得基内的个数最少。
基本操作
我们用数组 p 表示 {ai−1} 的线性基。
pi 的二进制最高位是第 i+1 位。
插入
如果 x 的第 i 位是 1,就必须要选 pi,否则不选。
必须选时,如果没有 pi,那么我们就让 pi←x,并结束。
否则 x←x⊕pi。
1 2 3 4 5 6
| void insert(int x){ for(int i = 60; ~i; i--) if(x & (1LL << i)) if(!p[i])return void(p[i] = x); else x ^= p[i]; }
|
最大值
我们的二进制最高位是依次递减的。
ans 表示目前的最大值。
那么如果 ans 的第 i 位是 0,那么选 pi 一定不劣,因为 2k>∑i=0k−12i。
1 2 3 4 5 6
| int xormax(){ int ans = 0; for(int i = 60; ~i; i--) ans = max(ans, ans ^ p[i]); return ans; }
|
第 k 小
如果我们选择高位后不会对低位影响,那么我们就可以像 BST 求第 k 小一样了。
所以我们要尽可能把 pi 除了第 i 的其他位去掉。
形如:
10001000
01100000
00010001
00000100
虽然不能全部去掉,但是我们的目的已经达到了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| int kth(int k){ if(f)return 0; for(int i = 0; i <= 60; i++) for(int j = i - 1; ~j; j--) if(p[i] & (1LL << j)) p[i] ^= p[j-1]; int ans = 0; for(int i = 0; i <= 60; i++) if(p[i]){ if(k & 1)ans ^= p[i]; k >>= 1; } if(k)return -1; return ans; }
|
复杂度
时空复杂度(单次):logn。