线性基学习笔记
lmrttx
2021-01-12 21:11:29
线性基解决的问题：
>给定n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。
线性基是一个数列。
有原数列：$a_1$,$a_2$...$a_n$，则它对应的线性基记为：$p_1$,$p_2$...$p_n$。
注意：线性基是一个数组。
~~为什么叫这奇怪的名字...~~
$p_i$的意义就是：**出现1的最高位为$i$的数，当然是在二进制的表示下。**
对于每个数，找出它最高位的1(在第 $i$ 位），从而得到$p_i$。
如果$p_i$为0，就加入线性基。
否则异或 $p_i$ 继续寻找。
在 $p$ 数组搞完后，**从高位往低位**，如果异或后答案变大，就异或，不然跳过。
得到最终答案。
不想证明。
[洛谷线性基模板](https://www.luogu.com.cn/problem/P3812)，代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 55
#define ll long long
ll n,ans,a[N],p[2*N];
void get(ll x){
for(int i=62;i>=0;i--){
if(!(x>>(ll)i))continue;
if(!p[i]){p[i]=x;break;}
x^=p[i];
}
}
int main(){
scanf("%lld",&n);
for(register ll i=1;i<=n;i++)
{scanf("%lld",&a[i]);get(a[i]);}
for(int i=62;i>=0;i--){
if((ans^p[i])>ans)ans=ans^p[i];
}
printf("%lld",ans);
return 0;
}
```
谢谢阅读。