线性基 —— 学习笔记

Posted by WildCow on March 21, 2018

写在前面



可能出于一种私心吧
有了一种想写学习笔记的打算
于是准备拿线性基开刀
霍霍
感谢以下巨牛博客对我的帮助

会有部分摘抄
如果令作者感到不快
请通过 about 中最下方的邮箱联系我
侵必删,侵必付


基础内容



有一类这样的问题
给出N个数, 要从中选出一个最大的子集,使这个子集 xor 出的数的值域与原来的数 xor 出数的值域相同

XOR 可以看出是模 2 域下的加法运算

如果把一个数转化为二进制, 对应成一个由 01 构成的向量, 所有这些向量就构成了一个线性空间
原问题就转化为求这个向量组对于 XOR 的极大线性无关组
我们把这样的一个极大线性无关组叫做线性基

然后有一个复杂度O(60*60n)的高斯消元
但是有更优雅的方式,复杂度为O(60n)

首先来证明一个性质:

取向量组中的两个向量 a, b
把 a, b中的某一个替换成 a xor b
替换前后向量组中的向量的线性组合得到的空间相同
通俗的说就是 替换前后 能异或出来的值一样


证明:

不妨把 b 替换成了 c = a xor b
对于一个值 x, 如果得到它不需要用到b,那么替换没有影响, 照样能得到x
如果需要 b, 而 b 可以通过 c xor a 来得到, 因此替换后照样能组合出x
也就是说 旧的向量组能组合出来的数 新的向量组也能组合出来

反过来,对于新的向量组,如果把c替换成 c xor a 就得到了旧的向量组
证毕

所以如果把向量组里的向量互相异或, 极大线性无关向量组的大小是不变的

所以有了这样一种构造方法:
从左往右扫描每个向量, 对于第 i 个向量的第 j 位, 如果前面已经有第 j 位为 1 的向量, 那么把第 i 个向量异或那个向量

这样最后得到的向量组, 不考虑 0 向量
最高位的 1 的位置是互不相同的
我们把 p[i] 表示最高位为第 i 位且为 1 的向量(从左往右标号)
显然这些向量线性无关

假设线性无关
那么构成第 i 个向量必须要含有 p[1] ~ p[i - 1] 的向量
因为 i + 1 以后的向量第 i 位均为 0
但是这样一来二进制 [1, i - 1] 的 1 就消不掉了= =!
所以假设不成立

于是这样构造出的极大线性无关组,也就是线性基,具有以下性质:

  • 性质一:最高位1的位置互不相同

  • 性质二:任意一个可以用这些向量组合出的向量x, 组合方式唯一

  • 性质三:线性基的任意一个子集异或和不为 0

关于性质一,由构造方法得显然

关于性质二
证明:
假设 x 的组合方法不唯一, 也就是说 x = a1 xor a2 ⋯ ap = b1 xor b2 ⋯ bq
那么 x xor x = 0 = a1 xor a2 ⋯ ap xor b1 xor b2 ⋯ bq

也就是说 可以用这个向量组里的向量组合出0向量, 与线性无关矛盾。 故组合方法唯一。

关于性质三,很显然= =!

构造代码:



void Guass()
{
	int cnt;

	cnt = 0;	///计算线性基元素的个数
    	for(int i = 1; i <= n; i ++){
            for(int j = 62; j >= 0; j --){
                if((ma[i] >> j) & 1){
                    if(!p[j]){
                	p[j] = ma[i]; 
                	break;
                    }
                    else{
                        ma[i] ^= p[j];
            	    }
                }
            }
        }
    for(int i = 0; i <= 62; i++){
    	if(p[i]){
    	    cnt ++;
    	}
    }
}




练习



  • hdu 3949

  • BZOJ2460

  • ~~BZOJ2115 ~~

  • CodeForces724G