ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

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

在处理异或问题时经常用到线性基,比如一个序列中某几个数的异或第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

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 模板 算法竞赛 线性基
最后更新:2022年8月3日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 定义 / Defination
  • 线性基三大性质
  • 线性基的构造方法
  • 重构 / Rebuild
  • 求最大异或和
  • 求第k小异或和
  • 例题

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号