线性基#

通过有限的线性基, 可以描述无限的线性空间.

算法竞赛中常用的线性基有两种, 实线性空间中的$\mathbb{R}^n$实数线性基和布尔域线性空间$\mathbb{Z}_2^n$中的异或线性基. (布尔域线性空间中加法为异或, 数乘为与).

以异或线性基为例, 我们可以根据一组布尔序列$X = \{x_1, x_2, ..., x_m\}$构造出一组异或线性基$B=\{b_1, b_2, ..., b_n\}$. 这组基有如下性质:

1. 任意非空子集的异或和不为0.
2. 对$X$中的任意元素$x$, 都可以在$B$中取出若干元素使其异或和为$x$.
3. $B$是满足性质1和2的极小向量组.

:::[异或线性基的典型用法]

1. 判断一个数是否能表示成某数集子集的异或和;
2. 求一个数表示成某数集子集异或和的方案;
3. 求某数集的最大/最小/第k大/第k小子集异或和;
4. 求某数在某数集子集异或和中的排名. :::