异或线性基学习笔记

前言

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

简介

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

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

基本操作

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

插入

如果 $x$ 的第 $i$ 位是 $1$，就必须要选 $p_i$，否则不选。

必须选时，如果没有 $p_i$，那么我们就让 $p_i \gets x$，并结束。
否则 $x\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];
}

最大值

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

那么如果 $ans$ 的第 $i$ 位是 $0$，那么选 $p_i$ 一定不劣，因为 $2^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 求第 $k$ 小一样了。
所以我们要尽可能把 $p_i$ 除了第 $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;
}

复杂度

时空复杂度（单次）：$\log n$。