线性基

written on 2022-08-14

学高斯消元的时候顺便学到了线性基，线性基通常在异或运算中出现。

这里先贴一下别人的博客，个人认为这篇博客总结的还是蛮好的，可以特别关注一下里面提到的基的含义以及线性基的性质。

线性基里面存了若干个元素，由这些元素互相异或就能够得到所有原序列异或得到的所有结果。与高斯消元类似的，线性基中的这些元素构成了一个 \(k\) 行 \(\log n\) 列的矩阵，其中的元素满足以下性质：

（节选自 oi 老前辈 menci 的学习笔记，写得真好%%%）

我代码中一般用 \(Ba\)（Basis） 来代替 其中的 \(a\)。

这个性质是不是和高斯消元最后的结果有点相似之处呢？

接着我们来看看一般线性基的构造代码：

I void Ins(ll x)
{
	for(int i=63;i>=0;i--)
	{
		if(!(x&(1ll<<i))) continue;
		if(!Ba[i]) return Ba[i]=x,void();
		x^=Ba[i];
	}
}

对于每一个元素执行 \(\tt{Ins}\)，最后得到的 \(Ba\) 数组存的就是线性基内的元素。

当然如果要把一般情况下的线性基转化为类似于高斯消元最后形式那样的，就要在主函数内再加入一句：

for(int i=0;i<=63;i++) for(int j=0;j<i;j++) if(Ba[i]&(1ll<<j)) Ba[i]^=Ba[j];

这种更高强度的线性基在求异或和第 \(k\) 大时会常用。

那么如何求异或最大值呢？考虑贪心，只要从高位向低位依次地取线性基内的元素就能够保证最优。正确性显然。

for(int i=51;i>=0;i--) if(!(ans&(1ll<<i))) ans^=Ba[i];

以上的内容相对来说并不是很难。当然关于线性基构造的正确性证明现在还看不太懂，以后再来填坑吧。。

下面来看看如何求异或第 \(k\) 大值。

关于这个问题，由于我太懒了懒得打就看一下这篇博客吧，写得也是蛮好的。注意这里的线性基即指更高强度的线性基，并且要特判一下线性基内是否有 \(0\)。（根据线性基的性质，线性基内任意元素的异或和均不为 \(0\)。）

给出代码：

I ll ask(ll x)
{
	if(cnt!=n) x--;//特判线性基内是否有 0 
	if((1ll<<cnt)<=x) return -1;
	ll res=0;
	for(int i=cnt-1;i>=0;i--) if(x&(1ll<<i)) res^=t[i];
	return res;
}
...
int main()
{
	...
   if(Ba[i]) t[cnt++]=Ba[i];
}

关于正确性的感性理解也在那篇博客里了，可以自己在手动模拟感受一下，还是挺妙的也。