一个线性基满足，对于它所表示的所有数的集合 ， 中任意多个数异或所得的结果均能表示为线性基中的元素互相异或的结果。
- 基中元素线性无关。
- 能表示原集合所有异或组合。
- 每个基元素最高位唯一。
构造方法
对于每一个数，我们找出他的最高位的 在第 位，如果此时 为零，就将这个数加入线性基，否则异或 继续找。
这样得到的线性基保证每一位都能有对应的最大值。
用途
插入
void insert(int x){
for(int i=50;i>=0;i--){
if((x>>i)&1){
if(!b[i]){
b[i]=x;
break;
}else x^=b[i];
}
}
}
求最大值
int query(){
int res=0;
for(int i=50;i>=0;i--){
if((res^b[i])>res)res^=b[i];
}
return res;
}
类似贪心的做法，如果x的当前位是0，那么异或一定会更优，否则当前位如果为1，则一定会更不优。
求最小值
inline ll qmin()
{
if(flag) return 0;
for(int i=0;i<=MAXN;++i)
if(a[i]) return a[i];
}
查询 是否在值域中
inline bool check(ll x)
{
for(int i=MAXN;i>=0;--i)
if(x&(1ll<<i))
if(!a[i]) return false;
else x^=a[i];
return true;
}
查询 小值
将 变成所有只有一位为一的数组，类似于高斯消元。
注意，上面这一步不能漏。
然后对应 的每一位，求值，相当于求每一位。
void build(){
for(int i=0;i<=60;i++){
for(int j=0;j<i;j++){
if(b[i]&(1ll<<j))b[i]^=b[j];
}
}
}
int query(int k){
build();
int cnt=0;
for(int i=0;i<=60;i++)if(b[i])cnt++;
if(cnt<n)k--;
// if(k<=0)return -1;
if(k>=(1ll<<cnt))return -1;
int res=0;
for(int i=0;i<=60;i++){
if(b[i]){
if(k&1)res^=b[i];
k>>=1;
}
}
if(k>0)return -1;
return res;
}
线性基合并
直接将 A 插入 B。
void merge(xxj &a, const xxj &b) {
for (int i=30;i>=0;i--)if (b.bb[i])a.insert(b.bb[i]);
}
P4151 [WC2011] 最大 XOR 和路径
这道题我们可以发现，很难计算的是环。我们发现一个环一定可以凭空走，也就是来到这个环，走一圈然后回去，其他就会抵消掉。所以我们想让环的异或值最大，并且要到达 。
于是我们随便选择一条 到 的路径，再选一些环。如果有多条 到 的路径也没有影响，因为这样 到 本身也就是一个环。
前缀和线性基
我们可以让一个线性基保存 的信息，差分求解。对于每一个位置，我们需要记录下来那个占用位置的数，数的 越小就越优先。
这样查询的时候我们只需要判断这个位置的 是否 就行了。
CF1100F Ivan and Burgers
这个就是前缀和线性基的模板题了，直接用上面的思路做就行了。
P3292 [SCOI2016] 幸运数字
很难想象题解中为什么会有那么多复杂的做法，前缀和线性基不是很好做吗？
这道题我们可以前缀设成到一的路径，然后套上 LCA，暴力合并两边的线性基就行了。
可删除线性基
P3733 [HAOI2017] 八纵八横
首先我们可以联想到 P4151 [WC2011] 最大 XOR 和路径 的那个算环的异或最大值的 trick。
但是这道题我们发现还有修改和删除操作，所以我们可能需要一个数据结构。
最容易想到的是线段树分治做法，这个比较简单。但是为了学习可删除线性基，所以我们还是学一下可删除线性基来维护这道题的答案。
可删除线性基是离线算法，我们记录每一个点删除的时间，用删除时间晚的替换删除时间早的。
P4869 albus就是要第一个出场
结论：每一个数出现的次数相同，次数为 。
分上下界可以证明，下界就选线性基以外的和线性基以内的匹配。