概念
- 线性基是一个集合。
- 从原集合中选取任意数都能通过线性基中的数异或得到。
本质上是对集合的压缩
性质
-
所有数字没有最高位相同的
-
集合大小为 \(\log_2\) 级别。
操作
排查:若线性基内有最高位相等的,让其相异或,并继续排查直到没有可操作的数。
若原集合内有 \(0\) 线性基无法实现。
实现
void insert(int x)
{
for(int i=62;i>=0;i--)
{
if(x&(1ll<<i))
{
if(xxj[i])
{
x^=xxj[i];
}
else
{
xxj[i]=x;
return;
}
}
}
return ;
}
标签:排查,int,笔记,学习,集合,异或,线性
From: https://www.cnblogs.com/lizhous/p/17372169.html