[数学基础 & 模板]Xor Linear Basis异或线性基学习笔记

2022年8月2日 169点热度 0人点赞 0条评论

在处理异或问题时经常用到线性基，比如一个序列中某几个数的异或第k大（小）值，判断某个数能否通过序列中的数字异或出来等。

定义 / Defination

在线性代数中，对于向量组 α1,α2,…,αn ，我们把其张成空间的一组线性无关的基成为该向量组的线性基。

而在我们学习算法的语境下，线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。

线性基三大性质

原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
线性基里面的任意一些数异或起来都不能得到0。
线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的。

线性基的构造方法

设数组p为a的线性基数组，下标从0开始，大约63个就够了。这里是将数字x进行二进制分解再插入到线性基数组中。注意要从大到小遍历，贪心的思想。

只需要这样写就可以了：

void ins(int x)
{
	for(int i = MAXL; i >= 0; -- i)//从大到小！
	{
		if(!x)return;
		if(!(x >> i & 1))continue;
		if(p[i])x ^= p[i];
		else
		{
			p[i] = x;
			break;
		} 
		
	}
}

这样构造的线性基并不完美，还需要进行一次重构，使得这个线性基更好。

重构 / Rebuild

void rebuild()
{
	tot = 0;
	for(int i = 0;i <= MAXL; ++ i)
	{
		for(int j = i - 1;j >= 0; -- j)
			if(p[i] >> j & 1)p[i] ^= p[j];
		
		if(p[i])d[tot ++] = p[i];
	}
}

求最大异或和

对于重构后的线性基，只需要将所有向量（数字）异或起来即可。

int que_max()
{
	int res = 0;
	for(int i = 0;i < tot; ++ i)res ^= d[i];
	return res;
}

求第k小异或和

如果要求第k大，就是求第(1 << tot) - k + 1小的异或和。注意要判断是否可以组合出0，举个例子，求最大异或和可以这么写：cout << que_min((1LL << tot) - (tot == N)) << endl;

int que_min(int k)
{
	if(tot != N)-- k;
	if(k >= (1LL << tot))return -1;
	
	int res = 0;
	for(int i = 0;i < tot; ++ i)if(k >> i & 1)res ^= d[i];
	return res;
}
cout << que_min((1LL << tot) - (tot == N)) << endl;