0.引入
令长度为\(n\)的有限集合\(S_0\in \mathbb{Z}\),考虑用01串表示其中的每个元素以及异或后可能产生的值,显然至少需要\(\lceil log_2 max(S_0)\rceil\)位来表示,同时会产生一个封闭集。
但是如果直接枚举生成需要枚举\(2^n\)次,因此需要一个更高效的表示方式。
1.线性基
线性基是用于表示集合\(S\)中的元素的基底,且\(S\)中元素由线性基中的元素互相异或产生。
举例: \(\{1, 2, 3, 4, 5, 6, 7\}\) 的一种线性基为 \(\{1, 2, 4\}\)。
2.例题
给定有限集合\(S\),求\(S\)的最大异或和。
先举个例子:\(S = \{1, 2, 3, 4, 5, 6, 7, 8\}\)
一眼可以看出必须包含\(8\)。为啥?因为如果不包含\(8\)那第\(4\)位上必为\(0\)。