浅谈线性代数合集

· · 算法·理论

说明

本文收录了 NOIP 级别的部分常用线性代数知识。

由于某些原因，小部分例题不放代码。

更新日志：

矩阵

Part 0：前置知识

Part 1：矩阵的基本定义和运算

1.1：矩阵的基本定义

其中，单位矩阵有一个性质：对于任意方阵 A_{n \times n}，满足 A \times I = I \times A = A。

相信细心的你可以发现，其实线性代数中的 I 就对应乘法中的 1，所以线性代数和初等代数是密切相关的。

1.2：矩阵的基本运算

矩阵加法：

将每一个矩阵元素相加，即 (A + B)_{i, j} = A_{i, j} + B_{i, j}，当且仅当两个矩阵行数列数完全相同才可使用。

例子：\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} + \begin{pmatrix} 1 & 1 \\ 4 & 5 \end{pmatrix} = \begin{pmatrix} 2 & 3 \\ 7 & 9 \end{pmatrix}。

矩阵数乘：

将每一个矩阵元素乘以该数，即 (kA)_{i, j} = k \cdot A_{i, j}。

例子：3 \times \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = \begin{pmatrix} 3 & 6 \\ 9 & 12 \end{pmatrix}。

矩阵乘法（\star）：

设矩阵 A_{m \times p}，B_{p \times n}，则乘积 C = A \times B 满足 C_{i, j} = \displaystyle \sum_{k = 1}^p A_{i, k} \cdot B_{k, j}（其中矩阵 C 大小为 m \times n）。

例子：\begin{pmatrix} 2 & 0 \\ 2 & 6 \end{pmatrix} \times \begin{pmatrix} 8 & 2 & 5 \\ 1 & 4 & 7 \end{pmatrix} = \begin{pmatrix} 16 & 4 & 10 \\ 22 & 28 & 52 \end{pmatrix}。

矩阵乘法满足结合律，即 (A \times B) \times C = A \times (B \times C)；矩阵乘法不满足交换律，即一般情况下 A \times B \neq B \times A。证明很简单，直接暴力带入计算即可。

::::success[Code]

struct Matrix {
  ll mtx[kMaxN][kMaxN];
  Matrix operator* (const Matrix &b) const {
    Matrix c;
    for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= k; ++ j) {
        c.mtx[i][j] = 0;
        for (int l = 1; l <= m; ++ l) {
          c.mtx[i][j] += mtx[i][l] * b.mtx[l][j];
        }
      }
    }
    return c;
  }
}

::::

作者建议，写矩阵乘法时和矩阵的结构体封装。

Part 2：矩阵快速幂算法

由于矩阵乘法满足结合律，我们便把快速幂的思想推广到矩阵当中。

借助快速幂的思想，我们可以推出结论：

对于方阵 A 和整数 k，设 k 的二进制位为 1 的位置是 p_1, p_2, \cdots, p_m，则 A^k = A^{2^{p_1}} \times A^{2^{p_2}} \times \cdots \times A^{2^{p_m}}。

于是，我们将初始矩阵设为单位矩阵 I（对应快速幂的初始值 1），然后将快速幂的整数乘法改为矩阵乘法即可。

::::success[Code]

struct Matrix {
  ll mtx[kMaxN][kMaxN];
  Matrix operator* (const Matrix &b) const {
    Matrix c;
    for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j <= n; ++ j) {
        c.mtx[i][j] = 0;
        for (int l = 1; l <= n; ++ l) {
          c.mtx[i][j] = (c.mtx[i][j] + mtx[i][l] * b.mtx[l][j] % kMod) % kMod;
        }
      }
    }
    return c;
  }
};

Matrix Qpow(Matrix a, ll k) {
  Matrix ans;
  for (int i = 1; i <= n; ++ i) {
    ans.mtx[i][i] = 1;
  }
  for (; k; k >>= 1) {
    if (k & 1) {
      ans = ans * a;
    }
    a = a * a;
  }
  return ans;
}

::::

设方阵的大小为 n \times n，则矩阵快速幂算法的时间复杂度为 \mathcal{O}(n^3 \log k)，其中快速幂的时间复杂度是 \mathcal{O}(\log k)，矩阵乘法的时间复杂度是 \mathcal{O}(n^3)。

Part 3：矩阵加速递推

我们在做递推或 DP 类题目时，如果答案的 n 很大（如 10^{18}）时，那么常规的 \mathcal{O}(n) 递推就会卡的你飞起来。

而矩阵是一个好东西，它可以大幅加速你的递推效率，一般会到 \log 级别。

为了更好的讲解，作者就拿斐波那契数列为例，它的递推式如下：

\begin{cases} f_1 = f_2 = 1 \\ f_n = f_{n - 1} + f_{n - 2} & (n \geq 3)\end{cases}

那么怎么用矩阵加速递推？在这之前，我们先要了解一个东西。

其实，矩阵的引入来自于线性方程组，而矩阵恰好体现了一种对数据打包处理的思想。

举个例子：

\begin{cases} 2x_1 + 3x_2 + 4x_3 = 11 \\ x_1 + 3x_2 + 5x_3 = 10 \\ 6x_1 + x_2 + x_3 = 14\end{cases}

根据矩阵乘法的原理，我们将上述方程组写成矩阵乘法的形式：

\begin{pmatrix} 2 & 3 & 4 \\ 1 & 3 & 5 \\ 6 & 1 & 1\end{pmatrix} \times \begin{pmatrix} x_1 \\ x_2 \\ x_3\end{pmatrix} = \begin{pmatrix} 11 \\ 10 \\ 14 \end{pmatrix}

虽然这些跟高斯消元有关系，但这跟矩阵加速递推的原理密切相关。

好了，回到正题。我们希望能从矩阵 \begin{pmatrix} f_{n - 1} \\ f_{n - 2} \end{pmatrix} 直接转移到矩阵 \begin{pmatrix} f_{n} \\ f_{n - 1} \end{pmatrix}。也就是需要构造一个矩阵 A 使得：

\begin{pmatrix} f_{n} \\ f_{n - 1} \end{pmatrix} = A \times \begin{pmatrix} f_{n - 1} \\ f_{n - 2} \end{pmatrix}

现在你就可以发现，这跟线性方程组的矩阵乘法形式一模一样！

那么考虑写出 f_n, f_{n - 1} 与 f_{n - 1}, f_{n - 2} 的关系：

\begin{cases} f_n = 1 \cdot f_{n - 1} + 1 \cdot f_{n - 2} \\ f_{n - 1} = 1 \cdot f_{n - 1} + 0 \cdot f_{n - 2}\end{cases}

把系数提出来，就可以得到初始矩阵 A：

A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}

现在，考虑将此矩阵递推式推广成 n 项。进行一些简单计算后，可以得到：

\begin{pmatrix} f_{n} \\ f_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n - 1} \times \begin{pmatrix} f_{1} \\ f_{0} \end{pmatrix}

带入 f_0 = 0 和 f_1 = 1 即可使用矩阵快速幂计算 f_n。

现在，线性递推的时间复杂度竟被神奇的降为 \mathcal{O}(\log n)（矩阵乘法的时间因矩阵太小而忽略不计）！

Part 4：例题

B2105 矩阵乘法 / P3390 【模板】矩阵快速幂

模板题，直接套就行了。

注意 P3390 要取模。

P1962 斐波那契数列

就是刚刚的例子，直接按照式子加上上面的模板即可。

::::success[Code]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 110;
const ll kMod = 1e9 + 7;

ll n;

struct Matrix {
  ll mtx[kMaxN][kMaxN];
  Matrix operator* (const Matrix &b) const {
    Matrix c;
    for (int i = 1; i <= 2; ++ i) {
      for (int j = 1; j <= 2; ++ j) {
        c.mtx[i][j] = 0;
        for (int l = 1; l <= 2; ++ l) {
          c.mtx[i][j] = (c.mtx[i][j] + mtx[i][l] * b.mtx[l][j] % kMod) % kMod;
        }
      }
    }
    return c;
  }
} f;

Matrix Qpow(Matrix a, ll k) {
  Matrix ans;
  for (int i = 1; i <= 2; ++ i) {
    ans.mtx[i][i] = 1;
  }
  for (; k; k >>= 1) {
    if (k & 1) {
      ans = ans * a;
    }
    a = a * a;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  f.mtx[1][1] = 1, f.mtx[1][2] = 1;
  f.mtx[2][1] = 1, f.mtx[2][2] = 0;
  cout << Qpow(f, n).mtx[2][1] << '\n';
  return 0;  
}

::::

P4838 P哥破解密码

这种题是见的比较多的，一般矩阵优化递推常常跟 DP 一起融合。

显然，令 f_{i, j} 表示以第 i 位结束，后缀极长连续 A 的长度为 j 的方案数（显然 j < 3）。

那么，容易得到转移方程（可以自己推一下）：

\begin{cases} f_{i, 0} = f_{i - 1, 0} + f_{i - 1, 1} + f_{i - 1, 2} \\ f_{i, 1} = f_{i - 1, 0} \\ f_{i, 2} = f_{i - 1, 1} \end{cases}

变一下形式：

\begin{cases} f_{i, 0} = 1 \cdot f_{i - 1, 0} + 1 \cdot f_{i - 1, 1} + 1 \cdot f_{i - 1, 2} \\ f_{i, 1} = 1 \cdot f_{i - 1, 0} + 0 \cdot f_{i - 1, 1} + 0 \cdot f_{i - 1, 2} \\ f_{i, 2} = 0 \cdot f_{i - 1, 0} + 1 \cdot f_{i - 1, 1} + 0 \cdot f_{i - 1, 2} \end{cases}

那么初始矩阵 A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}。

值得注意的是，答案需要将最终矩阵第一行的元素全部加起来，因为答案为 f_{n, 0} + f_{n, 1} + f_{n, 2}。

多测记得清空！

P2886 [USACO07NOV] Cow Relays G

挺有趣的一道题。

首先，我们观察一下 Floyd 的代码：

for (int k = 1; k <= n; ++ k) {
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
       f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    }
   }
}

是不是有点像矩阵乘法！

再看，发现有边的条数的限制。那么我们思考：假设我们有两个矩阵，如果其中一个矩阵代表恰好经过 a 条边的最短路，另外一个矩阵代表恰好经过 b 条边的最短路。那么将这两个矩阵合并就代表恰好经过 a + b 条边的最短路了。

怎么合并？我们魔改一下矩阵乘法：C_{i, j} = \min(C_{i, j},\ A_{i, k} + B_{k, j})，C 矩阵就是合并之后的矩阵。

这时候有人说，那不就转移 n - 1 次就可以了吗？

但是，结合矩阵乘法的雷霆复杂度，肯定会卡飞你。

那怎么办呢？我们复习一下矩阵快速幂的代码，里面的矩阵乘法是不是可以改为我们合并的过程呢？

这样我们转移 n - 1 次的复杂度就会被矩阵快速幂降为 \log 级别。

最后说一句，点的编号需要离散化。

::::success[Code]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 2020;

int n, t, s, e, cnt, c[kMaxN * kMaxN];

struct Matrix {
  int a[kMaxN][kMaxN];
  Matrix operator* (const Matrix &b) const {
    Matrix c;
    memset(c.a, 0x3f3f3f3f, sizeof c.a);
    for (int k = 1; k <= cnt; ++ k) {
      for (int i = 1; i <= cnt; ++ i) {
        for (int j = 1; j <= cnt; ++ j) {
          c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
        }
      }
    }
    return c;
  } 
} dis, ans;

void Qpow() {
  ans = dis;
  -- n;
  for (; n; n >>= 1) {
    if (n & 1) {
      ans = ans * dis;
    }
    dis = dis * dis;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> t >> s >> e;
  memset(dis.a, 0x3f3f3f3f, sizeof dis.a);
  for (int i = 1, u, v, w; i <= t; ++ i) {
    cin >> w >> u >> v;
    if (!c[u]) {
      c[u] = ++ cnt;
    }
    if (!c[v]) {
      c[v] = ++ cnt;
    }
    dis.a[c[u]][c[v]] = dis.a[c[v]][c[u]] = w;
  }
  Qpow();
  cout << ans.a[c[s]][c[e]] << '\n';
  return 0; 
}

::::

高斯消元

Part 0：前置知识

由 n 个未知数和 m 个一次方程组成的方程组称为 n 元一次线性方程组，常见形式为：

\begin{cases} a_{1, 1}x_1 + a_{1, 2}x_2 + \cdots a_{1, n}x_n = b_1 \\ a_{2, 1}x_1 + a_{2, 2}x_2 + \cdots a_{2, n}x_n = b_2 \\ \cdots \\ a_{m, 1}x_1 + a_{m, 2}x_2 + \cdots a_{m, n}x_n = b_m \end{cases}

Part 1：高斯消元的基础概念

1.1 增广矩阵

其实我们研究线性方程组本质上关注系数和常数项。为了简化，我们把系数和常数项组成增广矩阵，左侧是系数，右侧是常数项：

\left[\begin{array}{cccc|c} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} & b_1 \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} & b_2 \\ \cdots \\ a_{m, 1} & a_{m, 2} & \cdots & a_{m, n} & b_m\end{array}\right]

例如方程组：

\begin{cases} x + 2y = 5 \\ 3x + 4y = 11\end{cases}

对应的增广矩阵为：

\left[\begin{array}{cc|c} 1 & 2 & 5 \\ 3 & 4 & 11\end{array}\right]

1.2：初等行变换

高斯消元的本质是对增广矩阵做不改变方程组解的变换，即初等行变换（也有等价的初等列变换），有以下三种：

可以证明初等行变换不改变方程组的解。

1.3：行阶梯形矩阵

高斯消元的目标是将增广矩阵化为行阶梯形矩阵（每一行的主元都在上一行主元的右边），形如：

\left[\begin{array}{ccc|c} a_{1, 1} & a_{1, 2} & a_{1, 3} & b_1 \\ 0 & a_{2, 2} & a_{2, 3} & b_2 \\ 0 & 0 & a_{3, 3} & b_3\end{array}\right]

这样我们就可以从最后一行往上回代求解。

1.4：矩阵的秩

将矩阵化简为阶梯矩阵后，非零行的数量称之为矩阵的行秩（英文：rank）。

性质：行秩 = 列秩，统称为矩阵的秩。

矩阵的秩是判断线性方程组是否有解的重要工具。

情况 1：无解

系数矩阵的秩 < 增广矩阵的秩。

情况 2：无数解

增广矩阵的秩 < n。

情况 3：唯一解

系数矩阵的秩 = 增广矩阵的秩 = n。

读者可以自证锻炼思维。

Part 2：基础高斯消元的原理

以 n 个方程，n 个未知数的线性方程组为例，我们分两步实现高斯消元：前向消元，回代求解。

2.1：前向消元

目标：将增广矩阵化为上三角矩阵。

我们以三元方程组为例。

设原增广矩阵为：

\left[\begin{array}{ccc|c} a_{1, 1} & a_{1, 2} & a_{1, 3} & b_1 \\ a_{2, 1} & a_{2, 2} & a_{2, 3} & b_2 \\ a_{3, 1} & a_{3, 2} & a_{3, 3} & b_3\end{array}\right]

第一步：处理第一列。

  1. 选主元：找第一列中，从第一行开始往下绝对值最大的元素（可以避免浮点数精度误差），我们假设主元在第一行（a_{1, 1} \neq 0）。
  2. 消去第一列下方的元素：
    • 对第二行：计算系数 k_2 = \frac{a_{2, 2}}{a_{1, 1}}，执行 R_2 \to k_2 \times R_1，则第二行第一列变为 a_{2, 1} - k_2 \cdot a_{1, 1}；
    • 对第三行：计算系数 k_3 = \frac{a_{3, 1}}{a_{1, 1}}，执行 R_3 \to k_3 \times R_1，则第三行第一列变为 0。

此时，矩阵变为：

\left[\begin{array}{ccc|c} a'_{1, 1} & a'_{1, 2} & a'_{1, 3} & b'_1 \\ 0 & a'_{2, 2} & a'_{2, 3} & b'_2 \\ 0 & a'_{3, 2} & a'_{3, 3} & b'_3\end{array}\right]

第二步：处理第二列。

  1. 选主元：找第二列中，从第二行开始往下绝对值最大的元素（a'_{2, 2} \neq 0）。
  2. 消去第二列下方的元素：
    • 对第三行：计算系数 k_3 = \frac{a'_{3, 2}}{a'_{2, 2}}，执行 R_3 \to k_3' \times R_2，则第三行第一列变为 0。

此时，矩阵变为：

\left[\begin{array}{ccc|c} a''_{1, 1} & a''_{1, 2} & a''_{1, 3} & b''_1 \\ 0 & a''_{2, 2} & a''_{2, 3} & b''_2 \\ 0 & 0 & a''_{3, 3} & b''_3\end{array}\right]

2.2：回代求解

目标：从最后一行开始，依次计算每一个未知数的值。

求 x_3：最后一行对应的方程为 0x_1 + 0x_2 + a''_{3, 3}x_3 = b''_3，因此：

x_3 = \frac{b''_3}{a''_{3, 3}}

求 x_2：第二行对应的方程为 0x_1 + a'_{2, 2}x_2 + a'_{2, 3}x_3 = b'_2，因此：

x_2 = \frac{b'_2 - a'_{2, 3}x_3}{a'_{2, 2}}

求 x_1：第二行对应的方程为 a_{1, 1}x_1 + a_{1, 2}x_2 + a_{1, 3}x_3 = b_1，因此：

x_1 = \frac{b_1 - a_{1, 2}x_2 - a_{1, 3}x_3}{a'_{1, 1}}

Part 3：高斯-约旦消元法

上三角矩阵进一步优化，变成最简行阶梯矩阵可以使高斯消元的过程不需要回代，这就是高斯-约旦消元法。

具体来讲，就是每次在第行确定最大系数 a_{i, i} 后，将第 i 行的所有元素都除以 a_{i, i}，这样系数 a_{i, i} 就变为 1 了。然后，再将第 i 列上除了 a_{i, i} 以外的所有元素都消为 0，那么最后形成的增广矩阵，系数部分只有 a_{i, i} 是为 1（自由元是 0）的，每行的其他系数都为 0，那么第 i 个未知数 x_i 的解就是 a_{i, n + 1}。

::::success[Code]

const double eps = 1e-8;

void Gauss() {
  for (int i = 1, mxr; i <= n; ++ i) {
    mxr = i;
    for (int j = i + 1; j <= n; ++ j) {
      if (abs(a[j][i]) > abs(a[mxr][i])) {
        mxr = j;
      }
    }
    for (int j = i + 1; j <= n + 1; ++ j) {
      swap(a[i][j], a[mxr][j]);
    }
    if (abs(a[i][i]) < eps) {
      continue;
    }
    double div = a[i][i];
    for (int j = 1; j <= n + 1; ++ j) {
      a[i][j] /= div;
    }
    for (int j = 1; j <= n; ++ j) {
      if (j != i) {
        double rate = a[j][i];
        for (int k = i; k <= n + 1; ++ k) {
          a[j][k] -= rate * a[i][k];
        }
      }
    }
  }
}

::::

Part 3：例题

P3389 【模板】高斯消元法 / P2455 [SDOI2006] 线性方程组

模板题，套模板即可。

当存在自由元（无穷组解）时，有一个 i 满足 a_{i, i} = 0。

当无解时，有一个 i 满足第 i 行系数全为 0，但常数不为 0。

P5027 Barracuda

极水，枚举错误的是那一次称重，剩下的列方程高斯消元即可。

P4035 [JSOI2008] 球形空间产生器

根据提示，可以得到球面上的任何一点到球心距离相等。

所以考虑设球心坐标为 (x_1, x_2, \cdots, x_n)。

再结合题目给的公式，列出以下方程：

\begin{cases} (a_{1, 1} - x_1)^2 + (a_{1, 2} - x_2)^2 + \cdots (a_{1, n} - x_n)^2 = R^2 \\ (a_{2, 1} - x_1)^2 + (a_{2, 2} - x_2)^2 + \cdots (a_{2, n} - x_n)^2 = R^2 \\ \cdots \\ (a_{n, 1} - x_1)^2 + (a_{n, 2} - x_2)^2 + \cdots (a_{n, n} - x_n)^2 = R^2\end{cases}

相邻两个方程作差，得：

\begin{cases} \sum_{j = 1}^n [a_{1, j}^2 - a_{2, j}^2 - 2x_j(a_{1, j} - a_{2, j})] = 0 \\ \sum_{j = 1}^n [a_{2, j}^2 - a_{3, j}^2 - 2x_j(a_{2, j} - a_{3, j})] = 0 \\ \cdots \\ \sum_{j = 1}^n [a_{n, j}^2 - a_{n + 1, j}^2 - 2x_j(a_{n, j} - a_{n + 1, j})] = 0\end{cases}

移项，得：

\begin{cases} \sum_{j = 1}^n 2x_j(a_{1, j} - a_{2, j}) = \sum_{j = 1}^n(a_{1, j}^2 - a_{2, j}^2) \\ \sum_{j = 1}^n 2x_j(a_{2, j} - a_{3, j}) = \sum_{j = 1}^n(a_{2, j}^2 - a_{3, j}^2) \\ \cdots \\ \sum_{j = 1}^n 2x_j(a_{n, j} - a_{n + 1, j}) = \sum_{j = 1}^n(a_{n, j}^2 - a_{n + 1, j}^2)\end{cases}

这不就是高斯消元板子吗，直接暴力套板子！

线性基

Part 0：前置知识

Part 1：线性基的基本概念

1.1：线性基解决的问题

在算法竞赛中，异或是高频考点，而线性基是解决所有子集异或问题的重要工具。

如果说，现在给定 n 个正整数，让你求子集异或和的最大值。你直接来一句：“暴力！”。那完了，时间复杂度是 \mathcal{O}(2^n)，直接卡飞你。

但是，线性基可以将 n 个数压缩为最多 64 个基，所有子集异或和的结果等价于基的子集异或和，时间复杂度直接砍到 \mathcal{O}(n \log \text{max})（ \text{max} 为数字的最大位数）。

1.2：线性相关与无关（异或意义下）

定义：

Part 2：线性基的构造

2.1：线性基的性质

对于一个整数集合 S，其线性基 B 是满足以下条件的最小集合：

2.2：线性基的构造规则

虽然我们可以使用高斯消元来构造出线性基，但是这样时间复杂度较高，我们考虑使用构造。

假设线性基有 n 位，那么有数组 p = [p_1, p_2, \cdots, p_n]。数组元素 p_i 存储最高位为第 i 位的基元素，如果 p_i = 0 则表示该位没有对应的元素。

接下来，我们按照这些流程插入数字 x：

  1. 从最高位 n - 1 到最低位 0 遍历 x 的二进制位；
  2. 找到 x 的最高非零位 k；
  3. 如果 p_k = 0，直接将 x 存入 p_k，结束；
  4. 如果 p_k \neq 0，令 x = x \oplus p_k（也就是消去 x 的第 k 位），回到步骤 2；
  5. 如果 x 最终变为 0，说明 x 对线性基没有贡献。
  6. 如果你想求标准线性基，那么你需要对于求取的所有 p_i ，从低位到高位枚举，用低位的 1 消去所有高位的 1，确保每个 p_i 只有唯一的 1。

::::success[Code]

void Ins(ll x) { // 插入数字 x
  for (int i = 63; i >= 0; -- i) {
    if (x >> i) {
      if (!p[i]) {
        p[i] = x;
        break;
      } else {
        x ^= p[i];
      }
    }
  }
}

void Rebuild() { // 重构线性基
  for (int i = 63; i >= 0; -- i) {
    for (int j = i - 1; j >= 0; -- j) {
      if (p[i] & (1ll << j)) {
        p[i] ^= p[j];
      }
    }
  }
  for (int i = 0; i <= 63; ++ i) {
    if (p[i]) {
      d[cnt ++] = p[i];
    }
  }
}

::::

正确性证明请读者自证（比较简单）。

Part 3：例题

P3812 【模板】线性基

模板题，多一个求最大值。

想求最大异或值，就从最高位往低位一个个看线性基里对应这一位的数。如果把当前答案跟这个数异或一下，结果变得更大，那就更新答案。因为低位怎么变都影响不了已经确定的高位，所以这么做肯定是最优的。

P4570 [BJWC2011] 元素 / P3265 [JLOI2015] 装备购买

这两道题有着相似性，我们首先解决第一道题。

正确方法是先按魔力值排序，然后一个个插入，能插入的就把答案加上此矿石的魔力值。

怎么证明？

其实比较简单。因为对于两个同时可以存进第 k 位的数 a, b（假设 a < b），那么先插入 b 就可以保证第 k 位插入的元素魔力值最大。

于是就证完了。

再来解决第二题。

我们发现，这一题只是把第一问的数字改成了向量。

在异或线性基中，我们通过异或（XOR）把最高位消掉。那么，在实数线性基中，我们便可以使用四则运算抵消最高位，即：

c \to c - \frac{c_i}{p_{i, i}} \cdot p_i

于是，插入的代码就得出来了。

最后不要忘记这是向量！

::::success[Code]

void Ins(Node x) {
  for (int i = m - 1; i >= 0; -- i) {
    if (x[i]) {
      if (!p[i][i]) {
        p[i] = x;
        break;
      }
      x = x - p[i] * x.z[i] / p[i][i];
    }
  }
}

::::