江门市网站建设_网站建设公司_漏洞修复_seo优化

本篇将详细介绍基础的线性基模板

（文章非常详细，把笔者学时的每一个问题都详细解答了，如果感觉内容过于繁杂可以选择跳着看）

一：线性基及有关概念

线性相关：通俗讲，一个量a和b线性相关，则b一定可以表示为λ a

线性无关：即a和b非线性相关

线性基：维护一个极长线性无关基底，假设我们要通过一些数彼此异或，来表示[1,n]范围内的所有数，我们维护的这些数就叫做线性基，它的大小是严格log级别的。这里的线性相关:假设线性基是p（一个数组），数是x，若x和p线性相关，则x可以被p中某些元素彼此异或表示。

比如现在线性基里的元素有1,2，那么3一定不在线性基里，因为3=1^2,3和线性基p线性相关，所以不在里面

二：维护线性基

即将一个元素插入线性基的插入操作。

我们维护线性基时通常不把它看做一个数组，而是把它内的所有数二进制分解一下，看成一个矩阵，比如线性基里的元素有1,2,5,我们直接把它看成一个矩阵

二进制拆位：

我们如何表示一个线性基：设线性基是p,假如x在线性基内，设x的最高位1所在位数是i,那么p[i]=x

也就是把每个数存在最高位1所在位置

而线性基中不可能出现两个数最高位1在同一位，首先我们是这么构造的，其次也有证明：

使用反证法，设x和y是线性基的元素，最高位1在第k位

设z=x^y,由于x,y最高位是k,所以z<min(x,y)

假设z是p中某些元素pi彼此异或得到的结果，那么这些pi和x,y线性相关，这与线性基的定义彼此矛盾，故假设不成立

接着是插入操作：我们把一个元素插入线性基中，我们希望这个数能为线性基贡献一个新的基底，但这个数不能和线性基p线性相关，所以我们插入的数可能和原本的这个数不相同

具体插入操作如下：

插入x,设当前遍历x的第i位

1）：若x的第i位为0，直接看下一位

2）：若x的第i位是1，那么：

1]:线性基p的第i位有值，那么x^=p[i]，因为此时x和pi最高位1在同一位

2]:线性基p的第i位没有值，那么p[i]=x,结束插入，说明x找到了更低的最高位，直接插入即可

然后是查询最大值，我们从高到低遍历线性基p,,假设当前答案是res，

如果res的第i位是1直接跳过，因为pi的第i位也是1，而异或完会使值变得更小，因为损失了第i位，就算后面的所有位都是1，也不能弥补这一位变成0的损失

如果res的第i位是0，异或上pi，同理因为得到这一位，及时后面的位都损失了也是不亏的

【模板】线性基

代码如下：

#include<bits/stdc++.h> using namespace std; #define int long long #define _for(i,a,b) for(int i = a ; i <= b ; i ++) #define for_(i,a,b) for(int i = a ; i >= b ; i --) int n; const int maxn = 5e2 + 10; int p[maxn]; int a[maxn]; signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n; _for(i , 1 , n) cin >> a[i]; _for(i , 1 , n){ int x = a[i]; for_(j , 60 , 0){//插入线性基 if((x >> j) & 1){//x第j位是1 if(p[j]) x ^= p[j];//p第j位有值 else {//p[j]没值 p[j] = x;//插入 break; } } } } int x = 0;//最大值 for_(i , 60 , 0) x = max(x,x ^ p[i]); //其实是简略写法，和文章中所说的没有区别 cout << x; return 0; }

（本篇篇幅较小，主要是方便新手入门，下一篇是详细的线性基基础应用）