线性代数与高斯消元 (Linear Algebra & Gaussian Elimination)

线性代数（Linear Algebra） 在算法竞赛中是处理线性递推加速、多元一次方程组求解、概率期望图论建模以及异或空间基底的数学核心基石。

---

1. 矩阵运算与矩阵快速幂

1.1 矩阵乘法

设矩阵 \(A\) 的大小为 \(m \times k\)，矩阵 \(B\) 的大小为 \(k \times n\)，则它们的乘积矩阵 \(C = A \times B\) 的大小为 \(m \times n\)。其中每个元素满足：

\[ C_{i, j} = \sum_{r=1}^k A_{i, r} \cdot B_{r, j} \]

• 运算律：
• 满足结合律：\((A \times B) \times C = A \times (B \times C)\)；
• 满足分配律：\(A \times (B + C) = A \times B + A \times C\)；
• 绝不满足交换律：一般情况下 \(A \times B \ne B \times A\)。

---

1.2 矩阵快速幂加速线性递推

由于矩阵乘法满足结合律，我们可以利用二分快速幂在 \(\mathcal{O}(m^3 \log N)\) 的时间复杂度内计算方阵的 \(N\) 次幂 \(A^N\)（其中 \(m\) 为矩阵阶数）。

斐波那契数列极速递推：

斐波那契递推式为 \(F_n = F_{n-1} + F_{n-2}\)（\(F_1 = 1, F_2 = 1\)）。

将其构造成一阶状态向量与转移矩阵的形式：

\[ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} \]

通过数学归纳法展开：

\[ \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2} \begin{bmatrix} F_2 \\ F_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]

通过计算矩阵的 \(n-2\) 次幂，可将常数项线性递推的复杂度从 \(\mathcal{O}(N)\) 降至 \(\mathcal{O}(\log N)\)！

#include <vector>

using Matrix = std::vector<std::vector<long long>>;
constexpr long long MOD = 1e9 + 7;

Matrix multiply(const Matrix& A, const Matrix& B) {
    int n = A.size();
    int m = B[0].size();
    int k = B.size();
    Matrix C(n, std::vector<long long>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int p = 0; p < k; ++p) {
            if (A[i][p] == 0) continue;
            for (int j = 0; j < m; ++j) {
                C[i][j] = (C[i][j] + A[i][p] * B[p][j]) % MOD;
            }
        }
    }
    return C;
}

Matrix matrix_power(Matrix A, long long exp) {
    int n = A.size();
    Matrix res(n, std::vector<long long>(n, 0));
    for (int i = 0; i < n; ++i) res[i][i] = 1; // 单位矩阵

    while (exp > 0) {
        if (exp & 1) res = multiply(res, A);
        A = multiply(A, A);
        exp >>= 1;
    }
    return res;
}

---

2. 高斯消元法 (Gaussian Elimination)

高斯消元法通过对增广矩阵进行初等行变换，将一般的多元一次方程组化为上三角矩阵（或行简化阶梯形矩阵），从而确定解的存在性并求解。

2.1 解的三种可能状态判定

对于包含 \(n\) 个未知数、\(n\) 个方程的实数方程组： 1. 唯一解：消元后每行都有唯一的非零主元； 2. 无解：消元过程中出现行形如 \([0, 0, \dots, 0 \mid c]\)（其中 \(c \ne 0\)），即 \(0 = c\) 产生矛盾； 3. 无穷多解：消元后出现的有效非零行数 \(r < n\)，且不存在矛盾行。

#include <vector>
#include <cmath>
#include <algorithm>

constexpr double EPS = 1e-8;

// 返回值: 0: 唯一解, 1: 无穷多解, -1: 无解
// a 为大小为 n * (n + 1) 的增广矩阵，解保存在 ans 中
int gauss(std::vector<std::vector<double>>& a, int n, std::vector<double>& ans) {
    int row = 0;
    for (int col = 0; col < n; ++col) {
        // 1. 列主元选择: 选取当前列绝对值最大的行交换到当前行 (提高数值稳定性)
        int pivot = row;
        for (int i = row + 1; i < n; ++i) {
            if (std::abs(a[i][col]) > std::abs(a[pivot][col])) {
                pivot = i;
            }
        }

        if (std::abs(a[pivot][col]) < EPS) continue; // 当前列全为 0，跳过

        std::swap(a[row], a[pivot]);

        // 2. 将主元归一化为 1
        for (int j = n; j >= col; --j) {
            a[row][j] /= a[row][col];
        }

        // 3. 消去其余所有行该列的系数 (高斯-约旦消元)
        for (int i = 0; i < n; ++i) {
            if (i != row && std::abs(a[i][col]) > EPS) {
                double factor = a[i][col];
                for (int j = col; j <= n; ++j) {
                    a[i][j] -= factor * a[row][j];
                }
            }
        }
        ++row;
    }

    // 4. 检查解的合法性
    if (row < n) {
        for (int i = row; i < n; ++i) {
            if (std::abs(a[i][n]) > EPS) return -1; // 出现 0 = c (无解)
        }
        return 1; // 无穷多解
    }

    ans.resize(n);
    for (int i = 0; i < n; ++i) {
        ans[i] = a[i][n];
    }
    return 0; // 唯一解
}

---

3. 线性基 (Linear Basis) 与 异或空间

在处理子集异或和问题时，线性基（Linear Basis） 是处理异或向量空间的专用数据结构。

3.1 核心性质

设原集合为 \(S = \{a_1, a_2, \dots, a_n\}\)，其线性基为 \(B = \{b_0, b_1, \dots, b_{63}\}\)： 1. 张成空间等价：\(B\) 中的元素通过异或能够表示出的所有数值集合，与原数组 \(S\) 所有子集异或和集合完全相同； 2. 线性无关性：\(B\) 中任意非空子集的异或和均不为 \(0\)； 3. 极小性：若原数组最大数值在 64 位以内，线性基中最多只包含 \(64\) 个元素！

3.2 线性基标准模板

class LinearBasis {
private:
    std::vector<long long> basis;

public:
    LinearBasis() : basis(64, 0) {}

    // 插入一个元素，返回是否成功插入（若线性相关则插入失败返回 false）
    bool insert(long long x) {
        for (int i = 63; i >= 0; --i) {
            if ((x >> i) & 1) {
                if (basis[i] == 0) {
                    basis[i] = x;
                    return true;
                }
                x ^= basis[i];
            }
        }
        return false;
    }

    // 查询原集合所有子集异或和的最大值
    long long query_max() {
        long long res = 0;
        for (int i = 63; i >= 0; --i) {
            if ((res ^ basis[i]) > res) {
                res ^= basis[i];
            }
        }
        return res;
    }
};

---

4. LeetCode 经典真题精选与深度精析

• LeetCode 509 - 斐波那契数 (Fibonacci Number) 简单

  提示

  矩阵快速幂基石题。

  • 利用递推状态转移矩阵 \(\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\)。
  • 矩阵快速幂求解可以在 \(\mathcal{O}(\log N)\) 时间内完成。

• LeetCode 1137 - 第 N 个泰波那契数 (N-th Tribonacci Number) 简单

  提示

  三阶线性递推矩阵快速幂。

  • 递推式：\(T_n = T_{n-1} + T_{n-2} + T_{n-3}\)。
  • 转移矩阵为 \(3 \times 3\)：\(\begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}\)。
  • 时间复杂度 \(\mathcal{O}(3^3 \log N) = \mathcal{O}(\log N)\)。

• LeetCode 2851 - 字符串转换 (String Transformation) 困难

  提示

  KMP 匹配计数 + 矩阵快速幂加速状态转移。

  • 首先利用 KMP 算法求出字符串 \(s\) 在旋转后与 \(t\) 完全重合的旋转步数种数 \(c\)。
  • 每次操作：在其余 \(n-1\) 个位置中随机选择一个旋转步数。
  • 设 \(dp[k][0]\) 为 \(k\) 步后停留在匹配状态的方案数，\(dp[k][1]\) 为停留在不匹配状态的方案数。
  • 建立 \(2 \times 2\) 状态转移矩阵，使用矩阵快速幂计算 \(k\) 次转移。
  • 时间复杂度 \(\mathcal{O}(N + \log k)\)。