线性基

向量组：$x_1,x_2,\cdots,x_k$

线性空间：${a_1x_1+a_2x_2+\cdots + a_kx_k| a_i \in \R }$

线性空间是向量组的生成子空间，向量组是线性空间的生成子集

线性相关：$x_1$到$x_k$中某个向量$x_m$能被其他向量表示出来，即$x_m=a_1x_1+a_2x_2+\cdots+a_kx_k$，则向量组是线性相关的。

线性无关：$x_1$到$x_k$中任一向量不能能被其他向量表示出来，则向量组是线性无关的。

若一个向量组是线性无关的，则这个向量组是对应线性空间的基底，简称基，向量组的向量数量称为线性空间的维数。

若两个向量组${x_1,x_2,\cdots,x_n},{y_1,y_2,\cdots,y_m}$是等价的，则其中一个向量组的所有向量可以被另一个向量组表示出来，即$x_i=a_{i,1} y_1+a_{i,2}y_2+\cdots+a_{i,m}y_m,y_i=b_{i,1} x_1+b_{i,2}x_2+\cdots+b_{i,n}x_n$。

若要找出向量组 ${x_1,x_2,\cdots ,x_k}$ （不一定线性无关）的生成子空间的基，则可以使用高斯消元。

需要找出向量组的极大线性无关组，即找出最多的元素使得它们组成的向量组线性无关。通过高斯消元可以将向量组组成的矩阵消成上三角矩阵，则这些向量构成一组基，可以证明，基的数量一定小于等于 $d$ 个（ $d$ 表示向量的维度），因此查询时可以优化时间复杂度。

模板题：洛谷 P3812 【模板】线性基/AcWing 3164. 线性基

给定 $ n $ 个整数（可能重复），现在需要从中挑选任意个整数，使得选出整数的异或和最大。

请问，这个异或和的最大可能值是多少。

输入格式

第一行一个整数 $ n $。

第二行包含 $ n $ 个整数。

输出格式

输出一个整数，表示所选整数的异或和的最大可能值。

数据范围

$ 1 \le n \le 10^5 $,
$ 0 \le S_i \le 2^{63}-1 $

输入样例：

1 2

3 5 2 8

输出样例：

1

15

分析：

首先按位使用高斯消元求出基底，并使得基底的每个向量只有除了最高位都为零，则答案就是所有基底的异或和

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

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+5;

int n;
ll a[N];

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    
    int k=1;//高斯消元
    for(int i=62;i>=0;i--){
        for(int j=k;j<=n;j++){
            if(a[j]>>i&1){
                swap(a[j],a[k]);
                break;
            }
        }
        if(!(a[k]>>i&1))continue;
        for(int j=1;j<=n;j++){
            if(j!=k&&(a[j]>>i&1)){
                a[j]^=a[k];
            }
        }
        k++;
        if(k>n) break;
    }
    
    ll res=0;
    for(int i=1;i<=k;i++){
        res^=a[i];
    }
    cout << res;
    return 0;
}

例题：AcWing 210. 异或运算

给定你由 $ N $ 个整数构成的整数序列，你可以从中选取一些（至少一个）进行异或（$ \operatorname{xor} $）运算，从而得到很多不同的结果。

请问，所有能得到的不同的结果中第 $ k $ 小的结果是多少。

输入格式

第一行包含整数 $ T $，表示共有 $ T $ 组测试数据。

对于每组测试数据，第一行包含整数 $ N $。

第二行包含 $ N $ 个整数(均在 $ 1 $ 至 $ 10^{18} $ 之间)，表示完整的整数序列。

第三行包含整数 $ Q $，表示询问的次数。

第四行包含 $ Q $ 个整数 $ k_1,k_2,…,k_Q $，表示 $ Q $ 个询问对应的 $ k $。

输出格式

对于每组测试数据，第一行输出 Case #C:，其中 $ C $ 为顺序编号（从 $ 1 $ 开始）。

接下来 $ Q $ 行描述 $ Q $ 次询问的结果，每行输出一个整数，表示第 $ i $ 次询问中第 $ k_i $ 小的结果。

如果能得到的不同结果的总数少于 $ k_i $，则输出 $ -1 $。

数据范围

$ 1 \le N,Q \le 10000 $,
$ 1 \le k_i \le 10^{18} $

输入样例：

1 2 3 4 5 6 7 8 9

2 2 1 2 4 1 2 3 4 3 1 2 3 5 1 2 3 4 5

输出样例：

1 2 3 4 5 6 7 8 9 10 11

Case #1: 1 2 3 -1 Case #2: 0 1 2 3 -1

注意:只选取一个数字进行运算，则结果为该数字本身。