线性基的构造
线性基是怎么构造的?
大概就是考虑每个数 $a$,从高位到低位枚举,找到在线性基 $b$ 中没出现过的 $a$ 的最高位 $i$,将 $a$ 加入到线性基$b[i]$中,高于 $i$ 的 $a$ 的二进制位用线性基中的数给异或掉(因此此时 $i$ 就是 $a$ 的最高位了)。然后用类似高斯消元的方法,先用下面的行消自己,再用自己消上面的行,把线性基消成一个上三角矩阵。
线性基的性质
- 线性基中所有向量线性无关,也就是不能异或出 0(废话
- 线性基中每个对角线元素为 1 的列其余元素都为 0
- 若线性基中向量个数 $m <n$,那么存在向量组线性相关,可以异或出 0,总的异或和的个数为
$2^m$;否则,异或和个数为 $2^m - 1$ - 若线性基中向量个数 $m$,那么线性基中每个向量在原集合的异或和中出现的次数为 $2^{n-m}$
题目
最大异或和
将线性基中所有数异或起来即可。
1 |
|
k 大异或和
在线性基中找 $k$ 对应的二进制的异或和。
1 |
|
「WC2011」最大XOR和路径
结论:1 - n 的最大异或和路径,可以由任意 1 - n 异或和路径与图上一些环的异或得到。
挺显然的。。就是不会严格证明。
1 |
|
「HDU 6579」 Operation - 线性基
操作:在序列后面加入一个数、询问一个区间最大异或子序列,强制在线。
维护以每个位置结尾的线性基,再维护线性基中每一位的最右端点。插入时,尽量放右端点大的,然后将其他位向后移。查询时,在以 $r$ 结尾线性基中,用最右端点大于等于 $l$ 的更新答案。
1 |
|