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

发布于 2022-08-02  389 次阅读


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

定义 / Defination

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

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

线性基三大性质

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

线性基的构造方法

设数组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;

例题

P3857 [TJOI2008]彩灯 - 洛谷

Problem - 3949 XOR - HDUOJ

19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-08-03