线性基简记
约 200 个字 预计阅读时间 1 分钟
线性基¶
能够表示有限维线性空间 \(\mathbb{V}\) 的任意向量的一组向量称作线性基。
分类：
-
实数线性基：\(n\) 维实线性空间 \(\mathbb{R}^n\) 下的线性基。
-
异或线性基：\(n\) 维 \(bool\) 域的线性空间 \(\mathbb{Z}_2^n\) 下的线性基。
对于一个数组 \(arr_i\) 和其异或线性基 \(basis\)，可以通过 \(basis\) 数组内的数的异或 \((xor)\) 操作来表示出 \(arr_i\) 数组内的任意数。
如何构造线性基¶
-
贪心：考虑一个数组 \(arr_i\)，将其内每个数转化为二进制形式，OI Wiki。
-
高斯消元：解二进制线性方程组，得到的线性基矩阵是行简化阶梯形矩阵。
时间复杂度 \(O(nm)\)，实数线性基复杂度 \(O(n^2m)\)。