线性基学习笔记

Author Avatar
Sakits 4月 18, 2018

简介

  对于一个数集SS,线性基是一个集合β\beta满足β\beta中所有数互相异或得到的集合等价与SS中所有数互相异或得到的集合,也就是说可以将β\beta看成SS的一个压缩。
  首先向量组中的两个向量a,ba,b,将a,ba,b中的任意一个替换成a xor ba\ xor\ b,替换前后向量组中的向量的线性组合得到的空间相同,也就是能异或出的值一样,因为可以再异或一次得到原来的数。
  利用这个性质,我们就可以求出数集SS的线性基。

构造

for(int i=1;i<=n;i++)
{
	ll p=a[i].pos;
	for(int j=63;~j;j--) 
	if((p>>j)&1)
	{
		if(b[j]) p^=b[j];
		else {b[j]=p; break;}
	}
}

  高斯消元多一步把下三角消掉性质会更优,可以求第k大

inline void gauss()
{
	for(int i=1;i<=n;i++)
	{
		ll p=a[i];
		for(int j=63;~j;j--)
		if((p>>j)&1)
		{
			if(b[j]) p^=b[j];
			else {b[j]=p;break;}
		}
		if(!p) flag=1;
	}
	for(int i=63;~i;i--)
	{
		for(int j=i-1;~j;j--)
		if((b[i]>>j)&1) b[i]^=b[j];
	}
}

性质

  性质11:最高位1的位置互不相同。由上方构造方法可得。
  性质22:线性基的任意一个子集异或和不为00。由性质11可得。
  性质33:任意一个可以被异或出的值异或方案唯一。由性质22可得。

例题

  1.1.bzoj2460: [BeiJing2011]元素
  感性理解一下,xor后为0被丢掉的数一定是丢掉小的,所以把数字从大到小排序,依次用线性基判断是否会异或出0,不会就插入,计算答案,否则不插入不计算答案。
  2.2.hdu3949 XOR
  题目大意:查询可异或出的第kk小数。
  高斯消元求线性基,从高位到低位依次消元,如果有自由元说明00可以被异或出来,查询第kk大就查询kk二进制下的每一位,如果某一位ii上有11那么答案就异或上消元后第ii个数。
  3.3.bzoj4568: [Scoi2016]幸运数字