异或方程组线性基

jys posted @ Feb 03, 2014 09:18:20 PM in 未分类 , 2578 阅读

线性基linear base

for(int i=1;i<=n;i++)
for(int j=64;j>=1;j--)
{
	if(a[i]>>(j-1)&1)
	{
		if(!lb[j]){lb[j]=a[i];break;}
		else a[i]^=lb[j];
	}
}

用这个算法可以求出a数组的线性基

线性基就是原数组所能xor出的一切数这个线性基都能xor出来，不多不少

正确性显然

见莫涛PPT例六解法三

线性基的个数不超过log2V个，且对于每一位i，有且仅有一个线性基在这一位上是1（见构造过程）

注意到这个算法是在线的，可以随时插入一个新数

如果要支持在线的增加一个数/删除一个数/查询当前所有数的线性基二进制分组(sillycross的数据结构pdf)或者线段树可以做到一次操作O(64*lgn)

------------与XOR本身关系并不大的东西

一个无向图上的一条路径(u---...---v)的xor和，总可以被u到v的任意一条路径xor一些环的xor值得到

------------------------------------

有了这些东西之后基本上就能做题了

-----------------------------------

是看到最后一道题才突然发现自己这一块完全不懂的

#include <jystream>