算法笔记：线性基

ACM
1.8k words

网络赛被线性基典题暴打了，狠狠补一下。

一个线性基满足，对于它表示的所有数集合 SS，集合中任意一个数异或所得到的结果都可以表示为线性基中的元素互相异或的和。或者说，线性基可以找到一组数的子集，使得这些子集的异或和能够表示出所有可能的异或结果。

可以用于以下功能：

  • 快速查询一个数是否可以被一堆数异或出来
  • 快速查询一堆数可以异或出来的最大/最小值
  • 快速查询一堆数可以异或出来的第 kk 大值

具有一些性质：

  • 原数列里的任何一个数都可以通过线性基里的数异或表示出来
  • 线性基里任意一个子集的异或和都不为 00
  • 一个数列可能有多个线性基，但是线性基里数的数量一定唯一，而且是满足性质一的基础上最少的

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
template<typename T>
class LinearBasis{
private:
    int BITMAX;
    bool zero;  // 是否存在（能合成或自带的0）
 
    vector<T> b;
    bool outdate;
    
public:
    vector<T> p;
    void rebuild(){
        if (outdate==false)
            return ;
        int cnt=0;
        b.clear();
        for (int i=0;i<BITMAX;i++){
            for (int j=i-1;j>=0;j--)
                if (p[i]&(1LL<<j))
                    p[i]^=p[j];
            if (p[i])
                b.push_back(p[i]);
        }
        outdate=false;
    }
 
    LinearBasis(int BITMAX=sizeof(T)*8):
        BITMAX(BITMAX),zero(false),outdate(false){
        p.resize(BITMAX,0);
    }
    void insert(T x){
        for (int i=BITMAX-1;i>=0;i--){
            if (x&(1LL<<i)){
                if (!p[i]){
                    p[i]=x,outdate=true;
                    return ;
                }
                x^=p[i];
            }
        }
        if (x==0)
            zero=true;
    }
    bool check(T x){
        for (int i=BITMAX-1;i>=0;i--)
            if (x&(1LL<<i)){
                if (!p[i])
                    return false;
                x^=p[i];
            }
        return true;
    }
    T query_max(){
        T ans=0;
        for (int i=BITMAX-1;i>=0;i--)
            if ((ans^p[i])>ans)
                ans^=p[i];
        return ans;
    }
    T query_min(T k=1){
        k-=zero;
        if (k==0)
            return 0;
        rebuild();
        if (k>=(1LL<<b.size()))
            return -1;
        ll ans=0;
        for (int i=0;i<b.size();i++)
            if (k&(1LL<<i))
                ans^=b[i];
        return ans;
    }
    int size(void){
        rebuild();
        return b.size();
    }
};
 
void solve(void){
    LinearBasis<int> lbase;	// 不知道为什么如果写成全局变量，多组数据会有点问题
	
}
题目 备注
P3812 【模板】线性基 模板题，查询异或能出现的最大值。
acwing 异或运算 / hdu 3939 查询第k小值
[TJOI2008] 彩灯 查询异或结果的总数。
J - 找最小 2024CCPC网络赛 典题。查询异或结果最大值的最小值。
[P3265 JLOI2015]装备购买

Todo：

线性基题单

参考：https://www.luogu.com.cn/problem/solution/P3812