高斯消元与线性空间
cxyisjoker
·
2026-09-10 19:28:50
·
算法·理论
高斯消元
::::info[高斯消元]
高斯消元是求解线性方程组的一种方法。
:::info[线性方程组]
是由 M 个 N 元一次方程共同构成。
:::
::::
引入
在线性方程组中，对于其中一个式子（也就是说其中一行），有 N 个元（也就是说有 N 个系数）和一个等式右侧的常数。
所以，我们可以写出一个 M 行 N+1 列的增广矩阵。比如说：
f(x) = \begin{cases}
6x_1 + 2x_2 + 7x_3 = -6 \\
12x_1 + 4x_2 - 2x_3 = 15 \\
3x_1 + 9x_2 + 0x_3 = 6
\end{cases}
\Rightarrow
\begin{bmatrix}
\begin{array}{c c c|c}
6 & 2 & 7 & -6 \\
12 & 4 & -2 & 15 \\
3 & 9 & 0 & 6
\end{array}
\end{bmatrix}
在小学数学中我们学过“加减消元法”。
其实，这无非就是每次把其中一个式子乘上一个数和用一个式子的若干倍加（如果倍数为负数，就是减法）另一个式子。
这就差不多是我们所说的“初等行变换”。
具体来说，对于一个增广矩阵“初等行变换”有以下三条：
用一个非零的数乘某一行。
把其中一行的若干倍加到另一行上。
交换两行的位置。
我们接下来使用“初等行变换”来求解上面的方程。
\begin{bmatrix}
\begin{array}{c c c|c}
6 & 2 & 7 & -6 \\
12 & 4 & -2 & 15 \\
3 & 9 & 0 & 6
\end{array}
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
\begin{array}{c c c|c}
6 & 2 & 7 & -6 \\
0 & 0 & -16 & 27 \\
3 & 9 & 0 & 6
\end{array}
\end{bmatrix}
\Rightarrow \\\ \\
\begin{bmatrix}
\begin{array}{c c c|c}
6 & 2 & 7 & -6 \\
0 & 0 & -16 & 27 \\
0 & 8 & -\frac{7}{2} & 9
\end{array}
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
\begin{array}{c c c|c}
6 & 2 & 7 & -6 \\
0 & 8 & -\frac{7}{2} & 9 \\
0 & 0 & -16 & 27
\end{array}
\end{bmatrix}
\Rightarrow \\\ \\
\begin{bmatrix}
\begin{array}{c c c|c}
1 & \frac{1}{3} & \frac{7}{6} & -1 \\
0 & 1 & -\frac{7}{16} & \frac{9}{8} \\
0 & 0 & 1 & -\frac{27}{16}
\end{array}
\end{bmatrix}
我们把得到的这个矩阵叫做“阶梯型矩阵”，系数部分叫做“上三角矩阵”，名字来源于形状。这个矩阵表达着：
\begin{bmatrix}
\begin{array}{c c c|c}
1 & \frac{1}{3} & \frac{7}{6} & -1 \\
0 & 1 & -\frac{7}{16} & \frac{9}{8} \\
0 & 0 & 1 & -\frac{27}{16}
\end{array}
\end{bmatrix}
\Rightarrow
\begin{cases}
x_1 + \frac{1}{3}x_2 + \frac{7}{6}x_3 = -1 \\
x_2 - \frac{7}{16}x_3 = \frac{9}{8} \\
x_3 = -\frac{27}{16}
\end{cases}
显然，我们可以把 x_3 的值往回带，从而得到 x_2 ,在往回带，得到 x_1 。
\begin{bmatrix}
\begin{array}{c c c|c}
1 & \frac{1}{3} & \frac{7}{6} & -1 \\
0 & 1 & -\frac{7}{16} & \frac{9}{8} \\
0 & 0 & 1 & -\frac{27}{16}
\end{array}
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
\begin{array}{c c c|c}
1 & \frac{1}{3} & 0 & \frac{31}{32} \\
0 & 1 & 0 & \frac{99}{256} \\
0 & 0 & 1 & -\frac{27}{16}
\end{array}
\end{bmatrix}
\Rightarrow \\\ \\
\begin{bmatrix}
\begin{array}{c c c|c}
1 & 0 & 0 & \frac{215}{256} \\\ \\
0 & 1 & 0 & \frac{99}{256} \\\ \\
0 & 0 & 1 & -\frac{27}{16}
\end{array}
\end{bmatrix}
我们把得到的这个矩阵叫做“简化阶梯型矩阵”，系数部分叫做“对角矩阵”，名字来源于形状。
这个矩阵就是原方程的解。
介绍
如果你观察仔细，也会注意到其实高斯消元就是通过初等行变换把增广矩阵变为简化阶梯型矩阵的线性方程组的求解算法。
高斯消元的思想就是：对于每个未知量 x_i ,找到一个 x_i 的系数非零，但 x_1 \sim x_{i-1} 的系数全是 0 的方程，然后用初等行变换把其他方程的 x_i 的系数全部消成零。
特殊情况
无解
很显然，如果出现了 0x_1 + 0x_2 + \dots + 0x_n = q ，其中 q \neq 0 就是无解的。
无穷多解
还有一种可能是找不到 x_i 的系数非零，但 x_1 \sim x_{i-1} 的系数全是 0 的方程。
\begin{cases}
x_1 + 2x_2 - 1x_3 = 3 \\
2x_1 + 4x_2 - 8x_3 = 0 \\
-1x_1 - 2x_2 + 6x_3 = 2
\end{cases}
\Rightarrow
\begin{bmatrix}
\begin{array}{c c c|c}
1 & 2 & -1 & 3 \\
2 & 4 & -8 & 0 \\
-1 & -2 & 6 & 2
\end{array}
\end{bmatrix}
\Rightarrow \\\ \\
\begin{bmatrix}
\begin{array}{c c c|c}
1 & 2 & -1 & 3 \\
0 & 0 & -6 & -6 \\
0 & 0 & 5 & 5
\end{array}
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
\begin{array}{c c c|c}
1 & 2 & -1 & 3 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0
\end{array}
\end{bmatrix}
\Rightarrow \\\ \\
\begin{bmatrix}
\begin{array}{c c c|c}
1 & 2 & 0 & 4 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 0
\end{array}
\end{bmatrix}
显然，找不到 x_2 的系数非零，但 x_1 的系数是 0 的方程。
方程的解写作：
\begin{cases}
x_1 = 4 - 2x_2 \\
x_3 = 1
\end{cases}
发现 x_2 取任何值时，都对应着一个 x_1 。
我们把像 x_1 , x_3 这样的未知量称为“主元”。像 x_2 这样的未知量称为“自由元”。
可以发现，对于每个主元，整个简化阶梯形矩阵中有且仅有一个位置 (i,j) ，满足该主元的系数非零。第 j 列的其他位置都是零，第 i 行的第 1 \sim j-1 列都是零。
综上所述，在高斯消元完成后，若存在系数全为零、常数不为零的行，则方程组无解。若系数不全为零的行恰好有 n 个，则说明主元有 n 个，方程组有唯一解。若系数不全为零的行有 k < n 个，则说明主元有 k 个，自由元有 n - k 个，方程组有无穷多个解。
模板
P3389
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
double a[110][110];
int n;
int gauss()
{
int c, r;
for (c = 0, r = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ ) // 找绝对值最大的行
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
if (r < n)
{
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps)
return 2; // 无解
return 1; // 有无穷多组解
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0; // 有唯一解
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j <= n; j ++ )
{
cin >> a[i][j];
}
}
int ans = gauss();
if (ans == 1 || ans == 2)
{
cout << "No Solution";
}
else
{
for (int i = 0; i < n; i ++ )
{
cout << fixed << setprecision(2) << a[i][n] << endl;
}
}
return 0;
}例题
例题一
P4035
::::info[提示]
显然，学过~小学数学~的都知道，一个球体上的所有点到球心的距离相等，因此只需求出一个点 (x_1,x_2,\dots,x_n) ，使得：
\sum_{j=1}^n (a_{i,j}-x_j)^2 = C
其中 C 为常数，i \in [1,n+1] ，球面上第 i 个点的坐标为 (a_{i,1}, a_{i,2}, \dots , a_{i,n}) 。该方程组由 n+1 个 n 元二次方程构成，不是线性方程组。但是我们可以通过相邻两个方程作差，把它变成 n 个 n 元一次方程，同时消去常数 C ：
\sum_{j=1}^n \big(a_{i,j}^2 - a_{i+1,j}^2 - 2x_j(a_{i,j}-a_{i+1,j})\big) = 0 \quad (i=1,2,\dots,n)
把变量放在左边，常数放在右边：
\sum_{j=1}^n 2(a_{i,j}-a_{i+1,j})x_j = \sum_{j=1}^n \big(a_{i,j}^2 - a_{i+1,j}^2\big) \quad (i=1,2,\dots,n)
这就是一个线性方程组了。题目保证方程组有唯一解，我们直接对下面的增广矩阵进行高斯消元，变为简化阶梯形矩阵，即可得到每个 x_j 的值。
\begin{bmatrix}
\begin{array}{cccc|c}
2(a_{1,1}-a_{2,1}) & 2(a_{1,2}-a_{2,2}) & \dots & 2(a_{1,n}-a_{2,n}) & \displaystyle\sum_{j=1}^n(a_{1,j}^2-a_{2,j}^2) \\
2(a_{2,1}-a_{3,1}) & 2(a_{2,2}-a_{3,2}) & \dots & 2(a_{2,n}-a_{3,n}) & \displaystyle\sum_{j=1}^n(a_{2,j}^2-a_{3,j}^2) \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
2(a_{n,1}-a_{n+1,1}) & 2(a_{n,2}-a_{n+1,2}) & \dots & 2(a_{n,n}-a_{n+1,n}) & \displaystyle\sum_{j=1}^n(a_{n,j}^2-a_{n+1,j}^2)
\end{array}
\end{bmatrix}
:::info[代码]
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
int n;
double a[30][30],in[30][30];
void gauss()
{
int c, r;
for (c = 0, r = 0; c < n; c ++ ){
int t = r;
for (int i = r; i < n; i ++ )
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];
for (int i = r + 1; i < n; i ++ )
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
{
a[i][n] -= a[i][j] * a[j][n];
}
}
int main()
{
cin >> n;
for (int i = 0; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
cin >> in[i][j];
}
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
a[i - 1][j - 1] += 2 * (in[i][j] - in[0][j]);
a[i - 1][n] += in[i][j] * in[i][j] - in[0][j] * in[0][j];
}
}
gauss();
for (int i = 0; i < n; i ++ )
{
sec<< a[i][n] << endl;
}
return 0;
}例题二
P10499
::::info[提示]
设 x_i 表示第 i 个开关的操作情况，x_i = 1 表示按了这个开关，x_i = 0 表示没有按。再统计 a_{i,j} 表示第 i 个开关和第 j 个开关的联系情况，a_{i,j} = 1 表示按下 j 会影响 i 的状态，a_{i,j}=0 表示不会影响，特别地，令 a_{i,i} = 1 。
一个开关最后的状态 d_i ，取决于它最初的状态 s_i ，以及所有与它有联系的开关的操作情况执行异或运算得到的结果。可列出异或方程组：
\begin{cases}
a_{1,1}x_1 \operatorname{xor} a_{1,2}x_2 \operatorname{xor} \dots \operatorname{xor} a_{1,n}x_n = s_1 \operatorname{xor} d_1 \\
a_{2,1}x_1 \operatorname{xor} a_{2,2}x_2 \operatorname{xor} \dots \operatorname{xor} a_{2,n}x_n = s_2 \operatorname{xor} d_2 \\
\quad\vdots \\
a_{n,1}x_1 \operatorname{xor} a_{n,2}x_2 \operatorname{xor} \dots \operatorname{xor} a_{n,n}x_n = s_n \operatorname{xor} d_n
\end{cases}
异或其实就是不进位加法，我们仍然可以写出增广矩阵，矩阵中的每个值要么是 0 ，要么是 1 。然后，在执行高斯消元的过程中，把加、减法替换成异或，且不需要执行乘法。最终我们可以得到该异或方程组对应的简化阶梯形矩阵。若存在形如 0=1 的方程，则方程组无解。否则，因为自由元可以取 0 或 1 ，所以方程组解的数量就是 2^{cnt} ，其中 cnt 为自由元的个数。
在编写程序时，为了简便、高效，可以把增广矩阵的每一行进行状态压缩，用一个 int 类型的整数表示 n+1 位二进制数，其中第 0 位为增广矩阵最后一列的常数，第 1\sim n 位分别为增广矩阵第 1\sim n 列的系数。
:::info[代码]
#include <bits/stdc++.h>
using namespace std;
int n, a[50];
int gauss()
{
for (int i = 1; i <= n; i ++ )
{
for (int j = i + 1; j <= n; j ++ )
{
if (a[j] > a[i])
{
swap(a[j], a[i]);
}
}
if ( !a[i] ) return 1 << (n - i + 1);
if (a[i] == 1) return -1;
for (int j = n; j >= 1; j -- )
{
if (a[i] >> j & 1)
{
for (int k = 1; k <= n; k ++ )
if (i != k && (a[k] >> j & 1))
a[k] ^= a[i];
break;
}
}
}
return 1;
}
int main()
{
int t;
cin >> t;
while ( t -- )
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
for (int i = 1; i <= n; i ++ )
{
int u;
cin >> u;
a[i] ^= u;
a[i] |= 1 << i;
}
int x,y;
while ( (cin >> x >> y) && x != 0 && y != 0 )
{
a[y] |= 1 << x;
}
int res = gauss();
if (res == -1) cout << "Oh,it's impossible~!!\n";
else cout << res << "\n";
}
return 0;
}线性空间
定义
线性空间是关于向量加法 a+b （其中 a,b 均为向量）和标量乘法（也称数乘运算） k*a （其中 a 是向量，k 是常数）两个运算封闭的向量集合。
我们给定一些向量 a_1, a_2, \dots , a_k ，如果一个向量 b 能由 a_1, a_2, \dots , a_k 经过向量加法和标量乘法运算得出。我们称称向量 b 能被向量 a_1, a_2, \dots , a_k 表出。
显然，a_1, a_2, \dots , a_k 能表出的所有向量构成一个线性空间，a_1, a_2, \dots , a_k 被称为这个线性空间的。
基底与秩
我们任意选出一个线性空间里的一些向量，如果其中存在一个向量能被其他向量表出，我们称这些向量线性相关，否则我们称这些向量线性无关。
我们将线性无关的生成子集叫做“基底”，也可以叫它“基”。
如果你学过~小学数学~就会觉得很熟悉。
是的，这里只是把你学过的那个基底做了个扩充。
还有，基底的另一种定义是线性空间的极大线性无关子集 （好吧，其实差不多吧）。
:::info[啥，你不理解为什么叫这个名字？]
极大，其实就是最大吧,但不全是。
线性无关子集就是线性无关的生成子集。
合起来就是最大的线性无关的生成子集，而且要满足再加一个向量就会立刻线性相关。
一个线性空间的所有基底包含的向量个数都相等，这个数被称为线性空间的维数。
对于一个 n 行 m 列的矩阵，我们可以把它的每一行看作一个长度为 m 的向量，称为“行向量”。矩阵的 n 个行向量能够表出的所有向量构成一个线性空间，这个线性空间的维数被称为矩阵的“行秩”。类似地，我们可以定义“列向量”和“列秩”。实际上，矩阵的行秩一定等于列秩，它们都被称为矩阵的秩。
:::info[啥，你不知道为什么行秩等于列秩]
首先我们设这个矩阵是：
\begin{bmatrix}
A_{1,1} & A_{1,2} & \dots & A_{1,n} \\\ \\
A_{2,1} & A_{2,2} & \dots & A_{2,n} \\\ \\
\vdots & \vdots & \ddots & \vdots \\\ \\
A_{m,1} & A_{m,2} & \dots & A_{m,n}
\end{bmatrix}
我们设他的行秩为 r 。
则他的极大线性无关子集就是（我们设为 R ）：
\begin{bmatrix}
R_{1,1} & R_{1,2} & \dots & R_{1,n} \\\ \\
R_{2,1} & R_{2,2} & \dots & R_{2,n} \\\ \\
\vdots & \vdots & \ddots & \vdots \\\ \\
R_{r,1} & R_{r,2} & \dots & R_{r,n}
\end{bmatrix}
显然，对于每个向量我们都可以用 R 的向量表示：
x_1R_1 + x_2R_2 + \dots + x_nR_r
我们把表示系数的这个矩阵称作 P ：
\begin{bmatrix}
P_{1,1} & P_{1,2} & \dots & P_{1,r} \\\ \\
P_{2,1} & P_{2,2} & \dots & P_{2,r} \\\ \\
\vdots & \vdots & \ddots & \vdots \\\ \\
P_{m,1} & P_{m,2} & \dots & P_{m,r}
\end{bmatrix}
显然，A = PR 。
接下来，我们证明列秩小于等于 $r$。
显然，$A_j = PR_j$。
其中，$R_j, A_j$ 分别是 $R, A$ 的第 $j$ 列。
我们展开一下:
$$PR_j = P_1R_{1,j} + P_2R_{2,j} + \dots + P_rR_{r,j}$$
是不是十分的熟悉，我们写成这样:
$$R_{1,j}P_1 + R_{2,j}P_2 + \dots + R_{r,j}P_r$$
我们在变一下（用 $x$ 来代替）：
$$x_1P_1 +x_2P_2 + \dots + x_rP_r$$
哇，这不就是用基底表示向量得式子，只不过这里不是基地。
所以因为我们只用了 $r$ 个行向量，所以它真正的基底是小于等于 $r$。
显然，在求出基底后我们的其他的 $P_i$，可以用基底表示出来，在用分配率，这样刚刚的式子就化成用基底表示的。
所以，$A$ 的每个列向量都可以 $P$ 的基底表示出来。
所以 $A$ 的列秩小于等于 $r$, $A$ 的列秩小于等于 $A$ 的行秩。
接下来，我们证明一下反向不等式。
我们对矩阵等式 $A = PR$ 两边同时取转置。
根据矩阵转置运算法则：$(XY)^T = Y^T X^T$，得到：
$$
A^T = R^T P^T
$$
我们先看各个矩阵的维度：
- $A$ 是 $m\times n$ $\implies A^T$ 是 $n\times m$；
- $P$ 是 $m\times r$ $\implies P^T$ 是 $r\times m$；
- $R$ 是 $r\times n$ $\implies R^T$ 是 $n\times r$。
显然 $A^T$ 的**行向量**，就是原矩阵 $A$ 的**列向量**，$A^T$ 的**行秩** = 原矩阵 $A$ 的**列秩**，$A^T$ 的**列向量**，就是原矩阵 $A$ 的**行向量**，$A^T$ 的**列秩** = 原矩阵 $A$ 的**行秩**。
现在，我们把刚才对矩阵 $A$ 的整套论证，**原封不动套用到矩阵 $A^T$ 身上**。
设矩阵 $A^T$ 的行秩为 $r$。
按照前面同样的逻辑：
1. 取 $A^T$ 的行空间的极大线性无关行向量组，构成矩阵 $R'$；
2. 把 $A^T$ 的每一行表达成 $R'$ 的行向量的线性组合，得到系数矩阵 $P'$；
3. 写出分解式：$A^T = R' P'$；
4. 重复前面的推理，得到： $A_T$ 的列秩小于等于行秩。
这上面的你也可以理解为一开始如果我把矩阵竖着看呢？
做替换：
- $A^T$ 的列秩 = $A$ 行秩。
- $A^T$ 的行秩 = $A$ 列秩。
代入不等式：$A$ 行秩小于等于 $A$ 列秩。
再加上刚刚的 $A$ 列秩小于等于 $A$ 行秩。
所以，$A$ 的行秩等于 $A$ 的列秩。
继续讲定义。
:::
我们把这个 $n*m$ 的矩阵看作“系数矩阵”进行高斯消元（增广矩阵的最后一列全看作零）。
得到一个简化阶梯形矩阵。
显然，简化阶梯形矩阵的所有非零行向量线性无关。
因为初等行变换就是行向量之间进行的向量加法与标量乘法运算，所以高斯消元不改变矩阵的行向量表出的线性空间。
于是，简化阶梯形矩阵的所有非零行向量就是该线性空间的一个基底，非零行向量的个数就是矩阵的秩。、
~yes终于讲完了~，~哦不还有例题和异或空间~。
## 异或空间
我们将线性空间的概念进一步推广，不仅限于向量。
例如“异或空间”就是一个很常见的形式。
异或空间是一个关于异或运算封闭的非负整数集合。
我们可以在异或空间中定义“表出”“线性无关”“基底”等。
我们定义如果整数 $b$ 能由整数 $a_1,a_2,\dots,a_k$ 经异或运算得出，则称 $b$ 能被 $a_1,a_2,\dots,a_k$ 表出。
$a_1,a_2,\dots,a_k$ 能表出的所有整数构成一个异或空间，$a_1,a_2,\dots,a_k$ 被称为这个异或空间的生成子集。
任意选出异或空间中的若干个整数，如果其中存在一个整数能被其他整数表出，则称这些整数线性相关，否则称这些整数线性无关。
异或空间的基就是异或空间中一个线性无关的生成子集，或者定义为异或空间的极大线性无关子集。
给定 $n$ 个 $0 \sim2^m - 1$ 之间的整数 $a_1,a_2,\dots,a_n$，如何求出这 $n$ 个整数表出的异或空间的基？
:::info[答案]
我们可以把每个数看作 $m$ 位二进制数，写成一个 $n$ 行 $m$ 列的 $01$ 矩阵。
矩阵中第 $i$ 行从左到右依次是 $a_i$ 的第 $m-1, m-2, \dots, 1, 0$ 位（二进制数的最低位称为第 $0$ 位）。
把矩阵作为系数矩阵，用高斯消元求解异或方程组的方法，将其转化为简化阶梯形矩阵。
简化阶梯形矩阵的每一行也是一个整数，所有非零整数一起构成异或空间的基。
:::
## 例题
### 例题一
[P3265](https://www.luogu.com.cn/problem/P3265)
::::info[提示]
我们把 $n$ 件装备看作 $n$ 个长度为 $m$ 的向量。
根据题意，购买的装备对应的向量应该是线性无关的。
要买下最多数量的装备，其实就是求这 $n$ 个向量表出的线性空间的基底。
~好吧，这差不多是个板子~。
我们把 $a_{i,j}(1 \le i \le n,1 \le j \le m)$ 看作系数矩阵，则每个装备 $z_i$ 都是一个行向量。
用高斯消元求出该矩阵的秩，就得到了能买下的装备的最多数量。
但是！！！
本题还要求花最少的钱。
显然我们只需要在高斯消元的过程中，使用贪心策略。
对于每个主元 $x_i$，在前 $i-1$ 列为 $0$、第 $i$ 列不为 $0$ 的行向量中，我们可以选择价格最低的一个，消去其他行中第 $i$ 列的值。（在我给的模板中我求的是最大绝对值）
:::info[证明]
我们使用反证法
假设花费价钱最少的基底是 $z[i_1],z[i_2],\cdots,z[i_p]$，其中不包含价格最低的行向量 $z[k]$。
因为基底是极大线性无关子集，所以 $z[k]$ 能被 $z[i_1],z[i_2],\cdots,z[i_p]$ 表出，不妨设 $z[k] = b_1z[i_1] + b_2z[i_2] + \dots + b_pz[i_p]$。
移项可得 $z[i_p] = \frac{(z[k] - b_1z[i_1] - \dots - b_{p-1}z[i_{p-1}])}{b_p}$。
即 $z[i_p]$ 能被 $z[k]$ 和 $z[i_1],z[i_2],\cdots,z[i_{p-1}]$ 表出。
所以 $z[k],z[i_1],z[i_2],\cdots,z[i_{p-1}]$ 能与 $z[i_1],z[i_2],\cdots,z[i_p]$ 表出相同的线性空间，是一个总价格更低的基底，与假设矛盾。
:::
:::info[代码]
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-8;
int n, m, ct[510];
long double a[510][510];
int gauss()
{
int c, r, res = 0;
for (c = 1, r = 1; c <= m; c ++ )
{
int t = 0;
for (int i = r; i <= n; i ++ )
if (fabs(a[i][c]) > eps && (!t || ct[i] < ct[t]))
t = i;
if (!t) continue;
for (int i = 1; i <= m + 1; i ++ ) swap(a[t][i], a[r][i]);
swap(ct[r], ct[t]);
for (int i = m + 1; i >= c; i -- ) a[r][i] /= a[r][c];
for (int i = 1; i <= n; i ++ )
if (i != r && fabs(a[i][c]) > eps)
for (int j = m + 1; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
res += ct[r ++ ];
}
cout << r - 1 << " " << res;
return 0;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i ++ )
{
cin >> ct[i];
}
gauss();
return 0;
}
:::
::::
### 例题二
:::info[题目]
给定你由 $N$ 个整数构成的整数序列，你可以从中选取一些（至少一个）进行异或运算，从而得到很多不同的结果。
请问，所有能得到的不同的结果中第 $k$ 小的结果是多少?
:::
::::info[提示]
我们考虑将所有数变成二进制写在一起进行高斯消元，构造出异或空间的线性基。
构造完成后，对线性基进行化简，使得每个基底仅在自身最高位为 $1$，其余基底在该位都为 $0$。
设线性基中有 $cnt$ 个基底，则异或空间总共可以组合出 $2^{cnt} - 1$ 种不同的异或值。
将 $k - 1$ 转为二进制，二进制每一位代表是否选取对应位置化简后的基底，把选中的基底异或起来，就可以得到第 $k$ 小的异或值。
:::info[注意]
值得注意的一点边界情况是异或空间中第 $k$ 小的整数与题目中所求的第 $k$ 小的整数稍有不同。
题目不允许 $a_i \text{ xor } a_i$ 这样的运算，而异或空间中允许。
造成的差别是异或空间一定包含整数 $0$，但从 $a_1,a_2,\dots,a_n$ 选出几个不同的数异或，可能得不到 $0$。
实际上，我们检查简化阶梯形矩阵中是否存在“零行”，即可判断能否得到 $0$。
若不能得到 $0$，就把 $k$ 而不是 $k - 1$ 进行二进制分解（相当于在统计顺序时跳过“$0$”这个数）。
:::
:::info[代码]
```cpp
#include <bits/stdc++.h>
using namespace std;
unsigned long long a[10010];
int n, m, t;
int main()
{
int T;
cin >> T;
for (int Case = 1; Case <= T; Case ++ )
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
bool hz = 0;
t = n;
for (int r = 1, c = 1; c <= n; c ++, r ++ )
{
for (int i = r + 1; i <= n; i ++ )
{
if (a[i] > a[r])
{
swap(a[i], a[r]);
}
}
if (!a[r])
{
hz = true;
t = r - 1;
break;
}
for (int i = 63; i >= 0; i -- )
{
if (a[r] >> i & 1)
{
for (int j = 1; j <= n; j ++ )
{
if(j != r && (a[j] >> i & 1))
{
a[j] ^= a[r];
}
}
break;
}
}
}
cin >> m;
cout << "Case #" << Case << ":\n";
while (m -- )
{
unsigned long long k, ans = 0;
cin >> k;
if (hz)
{
k --;
}
if (k >= 1ull << t)
{
cout << "-1\n";
}
else
{
for (int i = t - 1; i >= 0; i -- )
{
if (k >> i & 1)
{
ans ^= a[t - i];
}
}
cout << ans << "\n";
}
}
}
return 0;
}
```
:::
::::
## 声明
本文章许多内容使用了《算法竞赛进阶指南》的内容（因为我是学这个的）。