线性基的定义
以上是官方给出的线性基的定义，但是需要一定的线性代数的基础，其实线性基很好理解，我们用下面一个例子去讲解
假设有3个数，1,2,3，我们这三个数互相异或总共有八种可能，我们能否找到一组数去表示非0的剩余的异或的结果，当然可以，我们可以发现用1,2就可以表示出来了，1自己异或是1,2自己异或是2,1,2异或是3
因此我们就可以说1,2就是这个方程的一组解，但是线性基未必只有一组，我们设想上面那个问题，是否1,3也可以去表示所有的非0异或解呢？
答案当然是肯定的
所以，简单来说，线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。
线性基的三大性质
线性基三大性质
1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到
2.线性基里面的任意一些数异或起来都不能得到 0
3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
但是还是有一个结论，如果求非0线性基中的第k小的数，我们可以将k转换为2进制，哪部分为1，就去base数组里第i个进行异或，最终结果就是第k小的
ps：这个方法只适用于高斯消元法，普通消元不适用
线性基的代码实现
普通消元法
普通消元法就是认为，有一个数组，长度最高位63位，然后我们不断读取一个新数，去看其第一位的一在哪一位，如果第一位的一所在的位数没有存数，那么就将这个数存进去，否则就用这个数去异或当前位上的那个数，不断异或，直到为0，或者找到一位，没有去存数位置
bool solve(int x)
{for(int i=62; i>=0; i--){if(x&(1LL<<i)){if(!d[i]){d[i]=x;return true;}else x^=d[i];}}return false;
}
类高斯消元法
就是类似于异或高斯消元，but是个一维数组，我们用一个len去统计有效区域，我们这个高斯消元的好处就是说可以极大的节省空间，我们完全不用看有效区域外的数，我们如果我们能够找到当前寻找位上是1的，我们就可以将其作为主元加入有效区域，然后拓展有效区域
void solve()
{len=1;for(int i=bit;i>=0;i--){int p=len;for(int j=len;j<=n;j++){if((base[j]>>i)&1LL){swap(base[len],base[j]);break;}}if((base[len]>>i)&1LL){for(int j=1;j<=n;j++){if(j==len){continue;}if((base[j]>>i)&1){base[j]^=base[len];}}len++;}}len--;
}例题：
P3812 【模板】线性基
题意：就是说给你n个数，让你求最大的异或值，这不就是线性基板题，直接套用模版就好了，我这里给出的是高斯消元方法的代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int bit=60;//设置数的最高位数
int base[55];//存储线性基的数组
int len;//去统计线性基的有效区间
int n;
void solve()
{len=1;for(int i=bit;i>=0;i--){int p=len;for(int j=len;j<=n;j++){if((base[j]>>i)&1LL){swap(base[len],base[j]);break;}}if((base[len]>>i)&1LL){for(int j=1;j<=n;j++){if(j==len){continue;}if((base[j]>>i)&1){base[j]^=base[len];}}len++;}}
}signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>base[i];}solve();int d = (1LL << n) - 1; int sum = 0;
// for(int i=1;i<=len;i++)
// {
// cout<<base[i]<<"\n";
// }for (int i = 1; i <= len; i++) {sum ^= base[i]; }cout << sum;return 0;
}P4570 [BJWC2011] 元素
贪心+线性基，代码虽然很短，但是思考过程还是有的，为什么从大到小排一遍然后放入线性基就是对的呢？
我们根据性质三可知，我们放入线性基的元素是固定的，也就是说，既然我们放的元素是一定的，那肯定是逮着最大的放啊，那你问，会不会因为先开始放入最大的而影响后面的，这肯定不会的啊，如果要将一个原来插入不进线性基的元素插入到线性基里面，只需要删去线性基里面的一个特定的元素就好了
所以就是贪心+线性基
这里用的是普通消元法
#include<bits/stdc++.h>
using namespace std;
#define int long longstruct node
{int x;//编号 int y;//值
};
node a[1010];
int n,ans=0;
int d[70];
bool cmp(node a,node b)
{return a.y>b.y;
}
bool add(int x)
{for(int i=62; i>=0; i--){if(x&(1LL<<i)){if(!d[i]){d[i]=x;return true;}else x^=d[i];}}return false;
}signed main()
{cin>>n;for(int i=1; i<=n; i++)cin>>a[i].x>>a[i].y;sort(a+1,a+n+1,cmp);for(int i=1; i<=n; i++){if(add(a[i].x))ans+=a[i].y;}cout<<ans<<'\n';return 0;
}#114. k 大异或和
就是说给你一个n，然后给你n个数，最后问你这n个数异或出来后，不重复的第k小的数是哪个
这题一眼线性基啊， ，但是需要用到我们上面那个第k小的结论，然后高斯消元法秒了
我们求出来的base数组是从1开始的，因此起始的是从大到小排序，因此我们需要转变一下下标位置，让其从小到大排序，然后用上面那个结论就可以过了
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int base[100005];
int a[200005];
int cnt = 0;
bool flag = false;
int bit = 60;
int len = 1;
void solve() {len = 1;for (int i = bit; i >= 0; i--) {for (int j = len; j <= n; j++) {if ((base[j] >> i) & 1LL) {swap(base[len], base[j]);break;}}if ((base[len] >> i) & 1) {for (int j = 1; j <= n; j++) {if (j == len)continue;if ((base[j] >> i) & 1LL) {base[j] ^= base[len];}}len++;}}len--;if (len == n)flag = false;else if (len < n)flag = true;
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> base[i];}solve();int cnt = 0;cin >> m;int sum = 0;int d = (1LL << len) - 1;for (int i = len; i >= 1; i--) {a[cnt++] = base[i];}for (int i = 1; i <= m; i++) {cin >> cnt;if (flag == true) {cnt--;}if (cnt > d) {cout << -1 << "\n";continue;}sum = 0;for (int i = 60; i >= 0; i--) {if ((cnt >> i) & 1) {sum ^= a[i];}}cout << sum << "\n";}return 0;
}我亲爱的小乖，我今天还是很想你，真想好好的陪你说话啊，你要加油哦
