浅谈异或线性基
yizcdl2357
·
·
个人记录
0. 前言
前置知识：按位异或运算的定义；基础的线性代数知识。
方便起见，下文用 \oplus 表示按位异或（\operatorname{xor}）。
1. 何为线性基？
我们给出一个向量的集合：
a_1=(1,2,3)
a_2=(2,3,4)
a_3=(3,4,5)
a_4=(1,3,6)
a_5=(1,4,9)
现在我们要求最少的若干个向量 b_1,b_2,\cdots,b_k（不必都从集合 a 里选取），使得集合 a 中每个向量都可以表示为 b 中某些向量的线性组合。
容易发现，k 的最小值为 3。我们可以如下构造 b 数组：
b_1=(1,2,3)
b_2=(1,1,1)
b_3=(-1,0,2)
它是符合要求的。因为：
a_1=b_1
a_2=b_1+b_2
a_3=b_1+2b_2
a_4=b_1+b_2+b_3
a_5=b_1+2b_2+2b_3
这个时候，我们称，集合 b 为集合 a 的线性基。
换句话说：若集合 a 中的每一个向量都能用集合 b 中的若干个（可为 0 个） 向量 线性组合出，且集合 b 是满足上述要求的元素个数最少的集合，那么称 b 是 a 的一个线性基。
要注意，一个向量集合的线性基往往不唯一。在上面的例子中，我们还可以这么构造 b 数组：
b_1=(2,3,4)
b_2=(1,1,1)
b_3=(0,1,3)
它也是符合要求的，显然它也是最小的。因为：
a_1=b_1-b_2
a_2=b_1
a_3=b_1+b_2
a_4=b_1-b_2+b_3
a_5=b_1-b_2+2b_3
类似的我们可以定义异或线性基：若集合 a 中的每一个数都能用集合 b 中的若干个（可为 0 个）数按位异或得出，且集合 b 是满足上述要求的元素个数最少的集合，那么称 b 是 a 的一个异或线性基。
和上一个差不多对不对？其实唯一的差别就在于：普通线性基是若干个向量的线性组合，异或线性基是若干个数的按位异或。
还是很抽象？举个例子：
a_1=3=(11)_2
a_2=8=(1000)_2
a_3=9=(1001)_2
a_4=10=(1010)_2
a_5=0
这时 k 的最小值是 3，异或线性基 b 数组如下构造：
b_1=1
b_2=2=(10)_2
b_3=8=(1000)_2
则：
a_1=b_1\oplus b_2
a_2=b_3
a_3=b_1\oplus b_3
a_4=b_2\oplus b_3
和普通线性基一样，一个集合的异或线性基也往往**不唯一**。在上面的例子中，我们还可以这么构造 $b$ 数组：
$b_1=1
b_2=3=(11)_2
b_3=11=(1011)_2
则：
a_1=b_2
a_2=b_2\oplus b_3
a_3=b_1\oplus b_2\oplus b_3
a_4=b_1\oplus b_3
# 2. 如何求异或线性基？
我们可以求一个特殊的异或线性基，使得线性基内任意两个数的**二进制最高位**不同。这种线性基具有很好的性质，比较容易求出。
**下文的“线性基”均指这种特殊的异或线性基。**
求线性基的核心思想是，把数一个一个依次插入线性基。
具体地说，如果一个数可以由已经出现在线性基里的数异或得到，那么这个数就不用加入线性基（否则违反了线性基“数的个数最少”这条性质）；
反之，如果目前线性基里的数不管怎么异或，都得不到这个数，那么就必须将它加进线性基里（否则这个数不能由线性基里的数异或得到）。
具体的实现需要开一个数组 `xxj[]` 储存所有的线性基：
`xxj[i]` 表示线性基中最高位为第 $i$ 位的元素（显然唯一）；
如果 `xxj[i]==0` 则表示线性基里还没有最高位为第 $i$ 位的元素。
将元素 $x$ 插入线性基里时，从高到低枚举 $x$ 的每一个二进制位。
假设枚举到第 $i$ 位。
- 如果 `xxj[i]==0`，那就说明 $x$ 的第 $i$ 位不能被目前线性基里的数异或出，所以必须把 $x$ 插入线性基，即 `xxj[i]=x`。
- 否则，我们要把 $x$ 的第 $i$ 位用 `xxj[i]` 消掉，也就是 `x^=xxj[i]`。（这就是为什么我们要让线性基内任意两个数的二进制最高位不同，因为这样才能起到消位的作用）
插入代码如下：
```cpp
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
struct xxj{
int a[51];
void insert(int x)
{
for(int i=50;i>=0;i--)
{
if((x&(1ll<<i))==0) continue;
if(a[i]>0) x^=a[i];
else
{
a[i]=x;
return;
}
}
}
};
xxj a;
int n,k;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>k,a.insert(k);
return 0;
}
```
如果不理解，可以自己举个例子手动模拟一下，亲测很有用。
**请确保理解了上文内容再往下继续。**
# 3. 这东西有什么性质？
1. 线性基没有异或和为 0 的子集。
2. 线性基中不同的异或组合异或出的数都是不一样的。
3. 线性基中每个元素的二进制最高位互不相同。
4. 对于原集合的任何一个子集的异或和，都存在线性基的恰好一个子集的异或和和它相等。（即，线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。）
# 4. 这东西有什么用？
## 1. 最大子集异或和
> 给定 $n$ 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。
先求出原集合的线性基，由于性质 4，我们只用选择线性基里面的数。
我们（贪心的）让答案的二进制高位尽可能为 $1$。
再看看性质 3：线性基中每个元素的二进制最高位互不相同。
那么思路就很明朗了：将线性基从高位向低位扫，假设扫到第 $i$ 位。
如果 $ans$ 的二进制第 $i$ 位为 $0$，那么就将 $ans$ 异或上 $xxj_i$ 以将第 $i$ 位变成 $1$，要不然 $ans$ 的第 $i$ 位就没机会变成 $1$ 了，不优。
```cpp
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
struct xxj{
int a[51];
void insert(int x)
{
for(int i=50;i>=0;i--)
{
if((x&(1ll<<i))==0) continue;
if(a[i]>0) x^=a[i];
else
{
a[i]=x;
return;
}
}
}
};
xxj a;
int n,k,ans;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>k,a.insert(k);
for(int i=50;i>=0;i--)
if((ans^a.a[i])>ans) ans^=a.a[i];
cout<<ans;
return 0;
}
```
习题：[P3812](https://www.luogu.com.cn/problem/P3812)（模板）
## 2. 异或和为 $0$ 的子集数目
> 给定 $n$ 个数，求这 $n$ 个数有几个子集（包括空集）的异或和为 $0$。
设线性基的大小为 $k$，下证答案为 $2^{n-k}$：
不在线性基里的数随便选，根据性质 4，线性基里的数恰好有一个子集可以和不在线性基里的数抵消为 $0$。
注意：有的题目空集不满足要求，这时候答案要减一。
```cpp
#include<iostream>
#include<cstdio>
#define int long long
#define M 1000000007
using namespace std;
int n,a,ans,xxj[51];
bool insert(int x)
{
for(int i=50;i>=1;i--)
{
if((x&(1<<i))==0) continue;
if(xxj[i]==0)
{
xxj[i]=x;
return 1;
}
x^=xxj[i];
}
return 0;
}
int P(int x)
{
if(x==0) return 1;
if(x&1) return 2*P(x^1)%M;
int t=P(x>>1);
return t*t%M;
}
signed main()
{
cin>>n;
ans=n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(insert(x)) ans--;
}
cout<<(P(ans)-1)%M;
return 0;
}
```
习题：[CF895C](https://www.luogu.com.cn/problem/CF895C)，[CF959F](https://www.luogu.com.cn/problem/CF959F)
# 5. 标号线性基及应用
**标号线性基**就是指，对于线性基的每一个元素，存储它是由原数组哪一个元素插进来的。
听起来很简单，实际上应用得还是比较灵活的，这里用一道例题做讲解。
> [P4570](https://www.luogu.com.cn/problem/P4570)：给定 $n$ 个物品，每个物品有两个属性 $a$ 和 $b$，你要取出一些物品，使其中没有 $a$ 的异或和为 $0$ 的子集，且所有物品的 $b$ 之和最大。
容易想到取出的物品一定是原物品的一个线性基。
因为根据定义，线性基没有异或和为 $0$ 的子集。
又根据定义，线性基一定是最大的满足上述要求的子集，所以 $b$ 之和一定也最大。
问题来了：一个序列有那么多个线性基，取哪个呢？
这里给出一个~~奇妙的~~贪心：
先将所有物品按 $b$ 从大到小排序，然后依次插入线性基，这样得到的线性基是最优的。
还有一个问题，如果我们求出线性基，要如何求出每个元素对应的 $b$ 是多少呢？
这个用标号线性基就可以解决了。
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
#define M 60
using namespace std;
int n,xxj[M+1],idx[M+1],ans;
struct ele{
int num,mag;
}a[1001];
bool cmp(ele x,ele y)
{
return x.mag>y.mag;
}
void insert(ele x,int num)
{
int y=x.num;
for(int i=M;i>=0;i--)
{
if((y&(1ll<<i))==0) continue;
if(idx[i]==0)
{
idx[i]=num;
xxj[i]=y;
return;
}
y^=xxj[i];
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].num>>a[i].mag;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
insert(a[i],i);
for(int i=0;i<=M;i++)
ans+=a[idx[i]].mag;
cout<<ans;
return 0;
}
```
习题：[P4301](https://www.luogu.com.cn/problem/P4301)，[P3265](https://www.luogu.com.cn/problem/P3265)，[CF1100F](https://www.luogu.com.cn/problem/CF1100F) 的在线做法（较难）
# 6. 线性基合并及数据结构维护
>**线性基合并**：给定 $a_1\sim a_n$ 的线性基 $A$ 和 $b_1\sim b_m$ 的线性基 $B$，求 $a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m$ 的线性基 $C$。
显而易见，将 $A$ 的所有元素插入 $C$，再将 $B$ 的所有元素都插入 $C$ 就行了。
复杂度 $O(\log^2 a_i)$（注意：**两只** $\log$）。
我们不妨把线性基的合并看作一种运算，显然它具有交换律、结合律，还是可重复贡献问题，所以可以用数据结构维护。
>[P4839](https://www.luogu.com.cn/problem/P4839)：有 $m$ 个初始为空的集合和 $2$ 种操作，第一种是把一个数加到一个集合里，第二种是查询集合 $l\sim r$ 的最大异或和。
用线段树维护线性基，每个节点 $[l,r]$ 储存集合 $l\sim r$ 的线性基。
显然节点 $[l,r]=$ 节点 $[l,mid]$ 和节点 $[mid+1,r]$ 之并。
查询时只要把所有涉及到的线段树节点并在一个新的线性基里就行了。
复杂度 $O(m\log^3n)$，~~经卡常~~可过。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define M 30
using namespace std;
int n,q,l,r,a[50001],xxj[200001][M+1];
inline void insert_num(int x,int y)//insert y to xxj[x][]
{
for(int i=M;i>=0;i--)
{
if(((y>>i)&1)==0) continue;
if(xxj[x][i]==0)
{
xxj[x][i]=y;
break;
}
y^=xxj[x][i];
}
}
inline void merge_xxj(int x,int y,int z)
{
for(int i=M;i>=0;i--)
insert_num(z,xxj[x][i]);
for(int i=M;i>=0;i--)
insert_num(z,xxj[y][i]);
}
inline void update(int idx,int l,int r,int x,int y)
{
if(x<l||x>r) return;
if(l==r)
{
insert_num(idx,y);
return;
}
int mid=(l+r)/2;
update(idx<<1,l,mid,x,y);
update(idx<<1|1,mid+1,r,x,y);
merge_xxj(idx<<1,idx<<1|1,idx);
}
inline void query(int idx,int l,int r,int x,int y)
{
if(r<x||l>y) return;
if(x<=l&&r<=y)
{
merge_xxj(0,idx,0);
return;
}
int mid=(l+r)/2;
query(idx<<1,l,mid,x,y);
query(idx<<1|1,mid+1,r,x,y);
}
int main()
{
cin>>q>>n;
while(q--)
{
int t;
scanf("%d%d%d",&t,&l,&r);
if(t==1)
update(1,1,n,l,r);
else
{
memset(xxj[0],0,sizeof(xxj[0]));
query(1,1,n,l,r);
int ans=0;
for(int i=M;i>=0;i--)
if((ans^xxj[0][i])>ans) ans^=xxj[0][i];
printf("%d\n",ans);
}
}
return 0;
}
```
习题：[CF1100F](https://www.luogu.com.cn/problem/CF1100F) [P5607](https://www.luogu.com.cn/problem/P5607) [P3292](https://www.luogu.com.cn/problem/P3292)
# 7. 总结
异或线性基是用来解决异或相关问题的一个算法，可以求最大子集异或和、异或和为 $0$ 的子集数目。
标号线性基可以解决一些异或与贪心相结合问题。
线性基合并方便将线性基搬到数据结构上维护，但时间复杂度较高。
# 8. [习题](https://www.luogu.com.cn/training/240930#information)
大致按从易到难排序。最后三题请谨慎食用。