线性基小结

用处

没用我学这东西干嘛

  • 快速查询一个数是否可以被一堆数异或出来
  • 快速查询一堆数可以异或出来的最大/最小值
  • 快速查询一堆数可以异或出来的第k大值

这么点?
还有点性质在下面 可能有点用

性质

  • 原数列里的任何一个数都可以通过线性基里的数异或表示出来
  • 线性基里任意一个子集的异或和都不为\(0\)
  • 一个数列可能有多个线性基,但是线性基里数的数量一定唯一,而且是满足性质一的基础上最少的

原理&实现

由于我想写简单一点,直接对代码写,所以真正的关于线性代数的那一部分就没写了 妄图掩盖自己不会的事实

约定

以下\(p[i]\)表示原序列的线性基数组。

构造

先贴代码
把一个数插入线性基:

inline void ins(LL x) {
	for(R int i=62;i>=0;i--)
		if(x&(1LL<<i)) {
			if(!p[i]) { p[i]=x,cnt++; break; }
			else x^=p[i];
		}
}

人话描述:

  • 从高位到低位进行。
  • 如果\(x_{(2)}\)第\(i\)位为\(1\),判断\(p[i]\)是否插入,没有就插入并且退出,否则就异或上\(p[i]\)去进行下一位操作 。

那么,通过观察这个构造,我们再来感性理解线性基。

  • 异或的一个小性质:$ x \oplus y \oplus y =x $。
  • 性质一:观察插入过程,如果没有成功插入,对于\(x_{(2)}\)的每一位,要不就是不存在,要不就是异或上\(p[i]\)变成了\(0\),那么最终\(x\)如果没有插入,那就意味着原有的线性基可以把它异或出来,它就没有插入的必要了。而更显然的,线性基中的数肯定是可以表示的。于是原序列中的每一个数都可以通过线性基表示出来。
  • 性质二:假设出现了\(p[1] \oplus p[2]\oplus p[3]=0\),那就会有\(p[1]\oplus p[2]=p[3]\),根据之前的定义,\(p[3]\)是不会被插入的。所以也可以得出线性基的任意一个子集异或和都不为\(0\),所以在之后求第\(k\)大的时候和一些别的时候,注意特判\(0\)
  • 性质三:考虑分类讨论
    • 当所有元素都可以插入线性基的时候,性质三显然成立
    • 设有一个元素\(x\)不能插入线性基,那就会有\(x=0\)或者是\(p[a]\oplus p[b]\oplus p[c]=x\)。显然当\(x=0\)的时候无论如何都不能插入线性基,而另一种情况则代表等式\(p[a]\oplus p[b]\oplus x=p[c]\)也就是说如果先插入\(x\),\(p[c]\)就无法插入了,又因为观察插入过程的时候,每一个插入的数对应着一位,所以\(x\)与\(p[c]\)相排斥只会影响一位上的问题,那也就代表着线性基里的数可能不同,但是总数肯定是一定的

于是我们初步理解了线性基

查询一个元素是否可以被异或出来

从高到低,如果这一位为\(1\)就异或上这一位的线性基,把\(1\)消去,根据性质一,如果最后得到了\(0\),那这个数就可以表示出来。

inline int ask(LL x) {
	for(R int i=62;i>=0;i--) 
		if(x&(1LL<<i)) x^=p[i];
	return x==0;
}

查询异或最大值

按位贪心即可。

inline LL askmx() {
	LL ans=0;
	for(R int i=62;i>=0;i--)
		if((ans^p[i])>ans) ans^=p[i];
	return ans;
}

查询异或最小值

其实异或的最小值一般来说就是线性基里的最小元素,因为插入这个元素的时候我们总是尽量让它的高位为\(0\)才来插入这一位。但是为什么是“一般”呢?因为有可能会有出现\(0\),得要在插入的时候记下个标记来特判才行。

inline LL askmn() {
	if(zero) return 0;
	for(R int i=0;i<=62;i++)
		if(p[i]) return p[i];
}

查询异或第\(k\)小

这个东东我感觉实现还是有那么点点复杂的哈。
首先考虑,要是每一位的选择都不会影响下一位的话,那就可以直接从高到低按位去选择就行了,就类似于二叉树求\(rank\)的玩法。但是我们之前建出来的线性基是没有这个性质的。比如\(p[3]=101_{2},p[0]=1_{2}\)的时候就炸了。所以我们考虑重构一个数组\(d\)来解决这个问题。先上代码:

inline void rebuild() {
	cnt=0;top=0;
	for(R int i=MB;i>=0;i--)
		for(R int j=i-1;j>=0;j--)
			if(p[i]&(1LL<<j)) p[i]^=p[j];
	for(R int i=0;i<=MB;i++) if(p[i]) d[cnt++]=p[i];
}

那么这是在干啥呢,就是在尽力把每个\(p[i]\)只留下第\(i\)位的\(1\),从而使得各个位之间互不影响,也就是说它的理想效果如下:
\(p[0] ~0~0~0~0~1\)
\(p[1] ~0~0~0~1~0\)
\(p[2] ~0~0~1~0~0\)
\(p[3] ~0~1~0~0~0\)
\(p[4] ~1~0~0~0~0\)
但有时候并不能达到这个样子,可能会出现如下情况:
\(p[0] ~0~0~0~0~1\)
\(p[1] ~0~0~0~0~0\)
\(p[2] ~0~0~1~0~0\)
\(p[3] ~0~1~0~0~0\)
\(p[4] ~1~0~0~1~0\)
但是这个时候我们注意到,我们的目的已经达到了,互不影响的任务已经达成了,显然此时为\(0\)的\(p\)值不会对排名有任何影响,不用管它了。把信息导入到\(d\)数组后,查询\(k\)小代码不难写出:

inline LL kth(int k) {
	if(k>=(1LL<<cnt)) return -1;
	LL ans=0;
	for(R int i=MB;i>=0;i--)
		if(k&(1LL<<i)) ans^=d[i];
	return ans; 
}

其实我个人觉得这个代码还得要自己理解一下。
背板子也行
但是这样其实还不太对,因为我们并没有考虑\(0\)的情况,所以还要去考虑一下\(0\)的情况,特判即可。

printf("%lld\n",tmp-zero?kth(tmp-zero):0LL);

于是线性基的基本操作就结束啦!

习题

  1. Luogu P3812 线性基
    code

  2. Luogu P3857 [TJOI2008]彩灯
    code

  3. Luogu P4301 [CQOI2013]新Nim游戏
    code

  4. Luogu P4570 [BJWC2011]元素
    code

  5. HDU 3949 XOR
    code

上一篇:java按照关键字指定的key删除redis(支持模糊删除)


下一篇:Nim积的一些东西