线性基学习

线性基介绍

有一个序列$A$，若存在一个序列$B$，使得对于$A$中任意若干个数的异或和$k$，一定有$B$中的若干个数，使得这些数的异或和为$k$，且$B$是满足以上条件的长度最小的序列，则称$B$为$A$的线性基。

线性基可以用来解决一些子集异或和的问题。

线性基的性质

1. 原序列的任意一个数都可以由线性基中的若干个数的异或和得到
2. 线性基中任意若干个数的异或和不为$0$
3. 在保持性质1的前提下，数的个数最少

线性基的构造

设数组$d$为数组$a$的线性基（$d$从$0$开始），则我们可以得到$d$的长度一定小于等于$a$中的最大数的二进制的位数。为什么呢？如果$d_i=2^i$，则如果$d$的长度与$a$中最大数的位数，则$a$中的每一个数都能按二进制位用$d_i$异或而得。

我们规定：若$d_i$不为$0$，$d_i$的最高位为$i+1$。当然，$d_i$为$0$表示$d_i$不存在。那么，我们可以构造数组$d$。

code

for(int i=1;i<=n;i++){
	for(int j=mx;j>=0;j--){
		if((a[i]>>j)&1){
			if(!d[j]){
				d[j]=a[i];
				break;
			}
			a[i]^=d[j];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

对于每个$a_i$，设$a_i$的最高位为$k$，若$d_{k-1}=0$，则将$a_i$赋给$d_{k-1}$，否则令$a_i=a_i\oplus d_{k-1}$。到最后一定能有若干个数能构成后来的$a_i$，那么用$a_i\oplus d_{k-1}$就能得到先前的$a_i$。

注：异或运算满足$a\oplus b\oplus b=a$

例题

有$n$个数组成的一个可重集合$S$，求一个集合$T\subseteq S$，使得$T_1\oplus T_2\oplus T_3\oplus \cdots \oplus T_{|T|}$最大。

• $n\le 10^5$
• $0\le S_i\le 2^{50}$

构造$S$的线性基$d$，显然$S$的最大异或和一定可以用$d$中的若干个数的异或和得到。

令答案为$ans$，$ans$的初始值为$0$。我们按$d$的下标从大到小遍历。对于每个$d_i$，若$ans\oplus d_i>ans$，则$ans=ans\oplus d_i$。为什么呢？在$i+1$位之前的的每一位不变的情况下，第$i+1$位如果是$0$，则将其变为$1$一定是更优的。因为在之后各个$a_i$的第$i+1$位一定为$0$，所以只有在这个数中才能将$ans$的这一位变为$1$。

• 若$ans$的第$i+1$位为$0$，则显然$ans\oplus d_i>ans$
• 若$ans$的第$i+1$位为$1$，则显然$ans\oplus d_i<ans$

所以我们可以通过$ans\oplus d_i$和$ans$的大小关系来决定是否要异或$d_i$。

code

#include
using namespace std;
int n;
long long ans=0,a[100005],d[55];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=50;j>=0;j--){
			if(a[i]&(1ll<<j)){
				if(!d[j]){
					d[j]=a[i];
					break;
				}
				a[i]^=d[j];
			}
		}
	}
	for(int i=50;i>=0;i--){
		if((ans^d[i])>ans) ans=ans^d[i];
	}
	printf("%lld",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27