抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

前言

本文的线性基指异或线性基。
由于作者太菜了本文的语言不会特别规范。

简介

线性基简称基,它是一个数的集合,并且每个序列都拥有至少一个线性基。
线性基有三个性质:

  1. 线性基中的几个数异或后不能得到 00
  2. 线性基中的数在异或后能得到原序列中的所有数。
  3. 线性基在保证前两个性质时,会使得基内的个数最少。

基本操作

我们用数组 pp 表示 {ai1}\{a_{i - 1}\} 的线性基。
pip_i 的二进制最高位是第 i+1i + 1 位。

插入

如果 xx 的第 ii 位是 11,就必须要选 pip_i,否则不选。

必须选时,如果没有 pip_i,那么我们就让 pixp_i \gets x,并结束。
否则 xxpix\gets x\oplus p_i

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];
}

最大值

我们的二进制最高位是依次递减的。
ansans 表示目前的最大值。

那么如果 ansans 的第 ii 位是 00,那么选 pip_i 一定不劣,因为 2k>i=0k12i2^k > \sum_{i=0}^{k-1}2^i

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 求第 kk 小一样了。
所以我们要尽可能把 pip_i 除了第 ii 的其他位去掉。
形如:
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\log n