线性代数 简明教程

JustPureH2O · 2024-01-23 17:20:05 · 学习·文化课

更好的阅读体验

本文 \LaTeX 量巨大，辛苦审核大大了。

前言

本文是 \texttt{Steven J.Leon} 所著《线性代数》（原书第十版）的简要总结与算法竞赛方面的扩充，适合线性代数入门者学习并把握线性代数的基本概念和内容。

需要注意的是：本教程中的矩阵表示方法可能与你在课上或是其他教程中看到的有些许出入。为了兼具美观和统一，单行行向量用圆括号包围，变量顶部用向量符号标记，如行向量：\vec a=\begin{pmatrix}1&2&3&4\end{pmatrix}，其余情况均以方括号包围；向量/一般变量用单一小写字母或符号表示，矩阵则用大写字母表示，如 2\times3 矩阵 B=\begin{bmatrix}1&3&-3\\0&-4&0\end{bmatrix}。

第一章 矩阵与方程组

相信大多数人入门线性代数的第一堂课就是学习如何利用矩阵求解线性方程组的吧。矩阵作为一个仅由数字和括号组成的表示方法，既避免了书写各种未知数符号的麻烦，也能一眼看出各未知量之间的数量关系，实属上乘的表示方法。矩阵的一些特殊性质也可以帮助我们解决一些难以解决的问题。

第一节 方程组与矩阵的互相转化

假设我们有一个方程组：\begin{cases}3x_1-x_3=8\\x_1-4x_2-x_3=-1\\-2x_1+x_2=5\end{cases}。首先将所有未知数提到等号左侧，常数全部移到右侧。我们暂时先忽略掉等号右边的常数项。我们将每行未知数的系数提取出来，放入矩阵的第一行，矩阵的第一行就表示方程组中第一个方程的未知数系数（没有默认为 0），以此类推到下边几行，最终你会得到一个列数与未知数个数相等、行数与方程个数相等的矩阵。本例中它长成这个样子：

如此得到的矩阵叫做系数矩阵，顾名思义，它只表示了原方程组的系数，而忽略了常数项。

它同时也是一个 3\times3 矩阵。

一般地，对于一个 n\times m 矩阵（n,m\in\mathbb N_+），它有 n 行 m 列。

此时，如果我们加上等号右侧的常数项，原先的 3\times3 矩阵会变成 3\times4 的。

人们为了区分常数和系数，选择在书写时将常数加入到最右侧那一列，并且在最右一列的前面加上竖线分隔系数，如此得到的矩阵叫做增广矩阵。

本例中 A 的增广矩阵形式 A^\prime 写作：

当矩阵元素不明时，我们为了简便表示矩阵本身，采用字母 + 下标 + 括号的方式。例如一个 i\times j 矩阵 A，可以写作：A=(a_{ij})。

第二节 矩阵的基本运算

一. 矩阵加法

构造相同的矩阵，即两个矩阵行列数相同，称这样的两个矩阵是同型的。

矩阵加法仅限两个同型矩阵，相加时同一行同一列的元素相加即可（增广矩阵同理）。

例如：\begin{bmatrix}1&0&2\\2&-1&3\\2&1&2\end{bmatrix}+\begin{bmatrix}-2&3&2\\0&1&1\\0&-1&3\end{bmatrix}=\begin{bmatrix}1-2&0+3&2+2\\2+0&-1+1&3+1\\2+0&1-1&2+3\end{bmatrix}=\begin{bmatrix}-1&3&4\\2&0&4\\2&0&5\end{bmatrix}

矩阵加法满足：结合律、交换律

二. 矩阵减法

矩阵减法是矩阵加法的逆运算，因此对于两个矩阵的形式要求同上，只是相同位置的元素相减而已。

矩阵减法满足：结合律、交换律

三. 标量乘法/矩阵数乘

矩阵的数乘也很简单，让矩阵中每个元素乘以这个数就可以了。

例如：4\cdot\begin{bmatrix}1&0&2\\2&-1&3\\2&1&2\end{bmatrix}=\begin{bmatrix}4\times1&4\times0&4\times2\\4\times2&4\times-1&4\times3\\4\times2&4\times1&4\times2\end{bmatrix}=\begin{bmatrix}4&0&8\\8&-4&12\\8&4&8\end{bmatrix}

矩阵数乘满足：交换律、结合律、分配律

四. 矩阵转置

将原矩阵的行变成新矩阵的列，称为矩阵的转置。

直观理解就是顺时针旋转 90 度后再水平镜像过去。转置用上标 T 表示。

例如：A=\begin{bmatrix}1&0&2\\2&-1&3\\2&1&2\end{bmatrix}，则 A^T=\begin{bmatrix}1&2&2\\0&-1&1\\2&3&2\end{bmatrix}

矩阵的主对角线（左上 - 右下）元素转置前后不变，且具有可逆性 [(A^T)^T=A]、数乘不变 [(k\cdot A^T)=k\cdot(A^T)]、分配律 [(AB)^T=A^TB^T]。

转置后恰好就是它自身的矩阵称为对称矩阵。它是自转置的，即 A^T=A。对称矩阵的元素恰好关于主对角线对称，且是一个 n\times n 的方阵。

五. 矩阵乘法

该内容将在第二章涉及。

第三节 消元

按照一般思路（就是我们在小学学的方法），我们会选择通过方程互相加减各自的倍数，达到消去未知数的目的。这种方法在矩阵上同样适用，而且它有一个贼高坤的名称：高斯消元法（Gaussian Elimination）。

回忆一下我们从出生就会用的消元原理，我们的目标就是让每个未知数都对应一个常数项，那么它的值就可以直接用常数除以系数的方式求出。矩阵中也是如此，为了能够化简出可直接求解的矩阵，我们在此引入初等行变换的概念：

1. 交换某两行
2. 把矩阵的某一行同乘以一个非零的数
3. 把某行的若干倍加和到另一行

这三条很容易理解。第一条：相当于交换方程组顺序，不影响计算；第二条：相当于对某一行方程放缩某倍，它等价于原方程；第三条：相当于前两条的融合，也是消元的关键一招。这三条规则在之后的初等矩阵内容中会再次出现。

首先从一个例子讲起，让读者感受一下初等行变换的魅力：

考虑这个方程组：

按照如上所述，将它转写成增广矩阵的形式：

我们总结一下常用的消元原理，应用到矩阵上就是：

1. 枚举每一列 c，选出无序组中第 c 列系数绝对值最大的一行 p，并移到无序组的最上边。（变换规则一）
3. 通过加减有序组中某一行的非零倍，将之后所有行的第 c 列系数化为 0。（变换规则三）

令矩阵 A=\left[\begin{array}{ccc|c}2&-1&1&1\\4&1&-1&5\\1&1&1&0\end{array}\right]（有序组用绿色表示）

枚举第一列，c=1。开始时，所有行均无序。选出绝对值最大的那一项，本例中为第二行，进行移动，原矩阵变为：

第二步，自乘并标记有序，因此第一行除以 4，原矩阵就变成了：

第三步，将无序组的第 c 列消成 0。本例中，我们让第二行减去二倍第一行；第三行直接减去第一行，得到：

枚举第二列，此时 c=2。第一步，选出第二列系数绝对值最大的那一行，移到无序组最上端。本例中无需移动，自乘 -\frac{2}{3}，标记有序，原矩阵为：

最终的最终，第三行减 0.75 倍第二行，得到我们心心念念的化简后的矩阵：

为什么把矩阵化简成这种金字塔型的形式呢？你会发现：最后一行仅有一个带系数的未知数 x_3，我们直接求，x_3=-1。向上一行，现在 x_3 相当于常数，移到常数中与 1 合并，x_2 也可直接求了……经过如上的反代操作，三个未知数都会被求出来。至此我们才发现这个三角形矩阵的魅力之处。

一般地，对于一个矩阵，如果它的非零系数呈阶梯形分布，则称这类矩阵为行阶梯形矩阵。将非零系数挑出来，它们组成的是一个上三角形矩阵；对应地，零项就会组成下三角矩阵。上三角矩阵通常以 U 表示、下三角矩阵通常用 L 表示。

原方程组有唯一解：

在这里，我没有给出代码实现。因为对于一些特殊情况，化简出的矩阵不能很好地被计算机处理，更适合算法竞赛体质的高斯消元模板将在本章第五节给出。

第四节 秩

类比一元二次方程的实数根存在性判别法 ——\Delta 判别式法，即对于一元二次方程 ax^2+bx+c=0，实数根的个数 =\begin{cases}0&b^2-4ac<0\\1&b^2-4ac=0\\2&b^2-4ac>0\end{cases}。那么，矩阵方程是否也有类似的根存在性判别方法呢？

答案是有的，而且不止一种，这意味着“矩阵是否有解” 这样的问题会有多种解决方案。现在介绍的是最为简单常用的一种——秩。

在线性代数中，一个矩阵 A 的列秩是 A 的线性独立的纵列的极大数目。类似地，行秩是 A 的线性无关的横行的极大数目。即如果把矩阵看成一个个行向量或者列向量，秩就是这些行向量或者列向量的秩，也就是极大无关组中所含向量的个数。

……咱们抛掉这种看也看不懂的高级语文句法，听我给你总结：

通俗来讲，把一个矩阵化成最简形式（特指行阶梯形）后，非零行的个数就是矩阵的秩。这其实是秩的最大线性无关组的定义。再次白话总结：如果存在三个行向量（列向量一样的，保证所有向量都是行 / 列向量即可）：\vec a=(1,2,3),\vec b=(2,4,6),\vec c=(-1,0,5)。根据高中数学中立体几何的知识 ——\vec a 和 \vec b 显然是共线的，这两个向量就是线性相关的。如果对于一组 n 维向量，可以成为 n 维空间的一组基底向量，那么它们就是线性无关的。

矩阵 A 的秩用 R(A) 表示，或者用 r(A)、rk(A)、rank(A) 等表示。

现在明白了吧，如果一个矩阵的某两行线性相关，它们都会被初等行变换第三条狠狠薄纱 —— 在乘或除以一个非零数后相减，其中一行就会被全部消成 0，从方程组角度来看就是 0x_1+0x_2+\dots+0x_n=0,n\in\mathbb N_+，带什么值都成立（相当于去重了一个方程）。

当然上边这一段也有表述不准确之处，假设有一个增广矩阵 A=\left[\begin{array}{ccc|c}1&2&3&2\\2&4&6&3\\-1&0&5&4\end{array}\right]。初等行变换第三条秒了第一、第二行，然而事情有些不对劲了……

第二行不乐意了，它还存留这最后一点倔强，好像在说：“你总结的不对呢真是雑鱼”。但是明眼人都看得出来，0x_1+0x_2+0x_3=-1 这种事情是绝对不可能发生的，也就是无解。按照刚刚说的，这个增广矩阵的秩 R(A^\prime)=3，可是它对应的系数矩阵 B^\prime=\left[\begin{array}{ccc}1&2&3\\0&0&0\\-1&0&5\end{array}\right] 的秩 R(B^\prime)=2，就有 R(A^\prime)\neq R(B^\prime) 且 R(A^\prime)>R(B^\prime)，于是我们就找到了矩阵无解的一个条件了。也就是 R(A)>R(B)。

再考虑有无穷解的情况：无非就是出现了 0x_1+k_2x_2+\dots+k_nx_n=s 的情况，此时 x_1 可以代任何值。与无解不同，这次的最简行阶梯形矩阵，无论是系数矩阵还是增广矩阵形式，它们的秩都是相同的，并且都浪费了至少一行方程式。我们知道：一个三元一次方程组是无法用相异的（行向量形式表示下不共线）两个方程解出唯一值的，相反，解形如：\begin{cases}x_1=2-x_2\\x_3=4\end{cases} 表明 x_1 由 x_2 确定、而 -x_2 又由 x_1-2 确定，然而这俩都不确定，导致这两个数可以取无穷多的值，也就导致矩阵有无穷组解。综上：矩阵有无穷组解的充要条件是 R(A)=R(B)<n（n 为未知数个数）。

最后就是有唯一解：如果一切进行顺利的话，既没有全零行，也没有无解行。那么此时系数矩阵和增广矩阵的秩会相同，且等于未知数个数，即 R(A)=R(B)=n。

总结，假设一个由 n 个未知数组成的最简行阶梯形矩阵 A、以及它的增广矩阵 B。矩阵解的个数由如下规则导出：

例 1.4.1 Delivery Mathematics 快递员的数学题

「稻妻狛荷屋的人气跨国快递员绮良良在送货途中遇到了一个难题，你作为无所不知无所不晓的旅行者自然是乐意地接下了她的委托。当你来到委托地点时，你发现这是一道解谜题目……」

稻妻号称最难的方块解谜是一组由 n,n\in\mathbb N_+ 个正方体可旋转方块组成的阵列，击打其中的某个方块会使得与之相关联的其他方块共同旋转一个特定角度。在这个谜题中，每个方块每次仅能水平顺时针旋转 90 度，传动方式在下图给出。问若要使所有方块同时朝向北方，需要如何击打方块？给出任意可行解，但需要保证每个方块旋转的次数不超过 4（不击打也可以，相当于次数为 0）。

由于钟离先生远在海那一头的璃月喝茶听评书、宵宫也正忙着制作夏日祭的烟花而无法抽身、香菱在万民堂做饭、安柏在侦察蒙德郊区、芙宁娜忙着吃蛋糕…… 总之没有其他人召唤物能帮你解决这个问题，你只能凭借自己的力量解开这个谜题。

问题分析：首先我们要搞清楚传动规则，我们会发现当你击打了一个方块，包括它在内、再按顺时针方向数两个方块都在旋转相同的角度。这也是这道题被称作难题的原因之一，只用想象力是很难想象的出来的…… 于是为了用代数方法解决该问题，我们选择用四个未知数、四个方程表示每个方块操作后的状态，问题解决的标志既为四个方块的状态均为 a（a 表示北方）。

算法设计：考虑到单个方块每旋转四次就相当于一次循环，因此我们重定义方向标，从北开始，顺时针方向将方位标记为 4n,4n+1,4n+2,4n+3(n\in\mathbb N)。这么做可以避免一些复杂的取模运算。接着我们根据传动规则表示每个方块的状态，令方块 1-4 被击打次数分别为 w,x,y,z。以方块 1 为例：击打自己、3 号和 4 号都会导致 1 号顺时针旋转 90°，再算上 1 号初始朝向为 2，得到：w+y+z+2=4n。其他方块以此类推，解析出的方程组对其求解即可。这样的矩阵一定有唯一解，每个未知数都以 n 表示，将一个自然数代入 n 值即可解出答案。

解：设方块 1-4 的击打次数分别为 w,x,y,z\in\mathbb N，设朝向从北方按顺时针方向分别为 4n,4n+1,4n+2,4n+3,n\in\mathbb N。

根据传动规则，有如下线性方程组：

增广矩阵形式为：

（化简过程略），行阶梯形式为：

因为系数矩阵的秩与增广矩阵的秩相同且都等于未知数个数 4，因此矩阵有唯一解 \begin{cases}w=\frac{4n-4}{3}\\x=\frac{4n+2}{3}\\y=\frac{4n+2}{3}\\z=\frac{4n-4}{3}\end{cases}。易知 n 的合法值满足 1+3k,k\in\mathbb N 的数学关系，此处求最小值，令 n=1，得到 \begin{cases}w=0\\x=2\\y=2\\z=0\end{cases}。

因此，最佳方案是暴击击打 2 号和 3 号方块各两次。

后日谈：有些读者可能会问，这个难道不是有无穷解吗？为什么上边说这个矩阵只有唯一解？其实这个矩阵确实只有唯一解，因为 R(A)=R(B)=4，造成它有无数组解的原因是 n 这个自然数。我们在开头只为这个矩阵设定了四个未知数 w,x,y,z，因此矩阵只有四个元，因而有唯一解。事实上，这个问题也可以转化成同余高斯消元，在普通高斯消元的基础上变除法为乘逆元即可。

对于有 p（质数）个有效旋转面的方块，详见洛谷 P10315，顺便推一下 我的题解。

第五节 计算机高斯消元

一. 实数高斯消元

基本思路与手推时相同：

1. 找到当前列元素绝对值最大的那一行，并移动到无序组的上端。
2. 将这一行的第一个元素除成 1。

此时需要进行一个神秘步骤：让除开当前行和第 c 列为零之外的所有行都用当前行消元一次。

如果有唯一解，我们会得到一个主对角线全为 1 的增广矩阵，此时每个未知数的结果就是右侧的常数。如果无解，还是像手推那样判断。如果存在无数组解，输出解的方法如下：

1. 枚举每一行，找到当前行第一个非零元素，并记录它的结果为右侧常数。该行的其余元素作为自由元，不作操作（或赋值为任意值）
2. 重复操作直到遍历到全零行。

我们会发现上三角矩阵中同一列可能有多个非零系数，这意味着上层方程组的结果依赖于下层的求解，如果出现自由元将会十分棘手。用上述方法将矩阵进一步化为对角矩阵后，就不会存在这种依赖关系了，因而判断和输出变得简单了许多。

核心代码如下：

int gauss() {
    int rank = 0; // 秩
    for (int c = 1, r = 1; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (abs(matrix[i][c]) > abs(matrix[t][c])) t = i; // 找出主元绝对值最大的那一行
        }
        if (abs(matrix[t][c]) < EPS) continue; // 非零才能消成1
        if (t != r) swap(matrix[t], matrix[r]); // 交换
        for (int i = n + 1; i >= c; i--) matrix[r][i] /= matrix[r][c]; // 主元消成1
        for (int i = 1; i <= n; i++) { // 反复消元，成为对角线矩阵
            if (abs(matrix[i][c]) > EPS && i ^ r) { // 当前行不消，若当前位已经是零了也不消
                for (int j = n + 1; j >= c; j--) {
                    matrix[i][j] -= matrix[i][c] * matrix[r][j]; // 消成零
                }
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 无解or无数组解
        for (int i = rank + 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (abs(matrix[i][j]) > EPS) return NO_SOLUTION; // 无解
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (abs(matrix[i][j]) > EPS) {
                    ans[j] = matrix[i][n + 1]; // 无数组解，找到主元并直接赋值，剩余的自由元自动赋值为0
                    break;
                }
            }
        }
        return INFINITE_SOLUTIONS;
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，此时常数项即为答案
    return UNIQUE_SOLUTION;
}

复杂度 \mathcal O(n^3)。

二. 同余高斯消元

上一节的例题就是同余高斯消元的一个典例，我们需要求解模 m 意义下 n 元非齐次线性方程组的特解（即每个未知数的解均在 [0,m) 之内）。本质上和上面的高斯消元是一样的，不同的一点是我们需要把除法换成逆元，而且需要对减法取模格外小心；对于 m 不为质数的情况，还需要额外考虑是否存在逆元。代码与上面雷同，不放了。

复杂度 \mathcal O(n^3)。

三. 异或高斯消元

适用于方程组和奇偶性相关联的时候，此时列出的方程组是异或和起来的。鉴于方程组的系数只有 0/1，我们的判断和消元也会简单许多，只需判断当前元素是否为 1。实践时一般使用 bitset 来优化时间复杂度。

int gauss() {
    int rank = 0; // 矩阵的秩
    for (int c = 1, r = 1; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (matrix[i].test(c)) {
                // 找到绝对值最大的行（只要第一个系数是 1 即可）
                t = i;
                break;
            }
        }
        if (!matrix[t].test(c)) continue; // 跳过零行
        if (t ^ r) swap(matrix[r], matrix[t]); // 交换到第一行

        for (int i = 1; i <= n; i++) {
            // 与普通高斯消元的不同之处，对 1~n 行全部消元
            if (matrix[i].test(c) && i ^ r) {
                // 当前行不消，零行不消
                matrix[i] ^= matrix[r]; // 异或代替减法进行消元
            }
        }
        r++;
        rank++;
    }
    if (rank < n) {
        // 秩小于 n，可能是无数组解、有可能无解
        for (int i = rank + 1; i <= n; i++) {
            if (matrix[i].test(n + 1)) return NO_SOLUTION; // 存在类似于 0=k 的矛盾情况，无解
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n + 1; j++) {
                if (matrix[i].test(j)) {
                    // 无数组解，找到主元并赋值
                    ans[j] = matrix[i][n + 1];
                    break;
                }
            }
        }
        return INFINITE_SOLUTIONS;
    }
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1]; // 有唯一解，对角矩阵每个未知数的解就是常数项的值
    return UNIQUE_SOLUTION;
}

复杂度 \mathcal O(\frac{n^3}{\omega})。

洛谷习题：

1. P3389 [模板] 高斯消元法
2. P2455 [SDOI2006] 线性方程组
3. P4035 [JSOI2008] 球形空间产生器
4. P10315 [SHUPC2024] 原神，启动！
5. P6126 [JSOI2012] 始祖鸟
6. P2447 [SDOI2010] 外星千足虫

第二章 矩阵乘法

第一节 什么是矩阵乘法

你经常能在各种线性代数的书上看到这样一串定义式：(BA)_{ij}=\sum\limits_{i=1}^{p}a_{ik}b_{kj}。这对于自学者（比如说我自己）其实是非常不友好的。他们在举例计算时很容易被 i,j,k 绕进去，不仅计算速度慢不说，还很容易出错…… 那我在此举出一个简记方法：

将左边的矩阵的每一行看作每个未知数都代了确定值的方程、右边的矩阵每一列看作是前者方程的未知数系数。二者相乘本质上就是让未知数和系数匹配上，并计算出结果放入结果矩阵的特定位置。这个特定位置也有讲究，假如选择了前一个矩阵的 i 行和后一个矩阵的 j 列进行运算，求和过后的答案应该放在答案矩阵的 (i,j) 位置。看以下例子来加深理解：

那么什么样的矩阵才能进行乘法运算呢？答案是一个 n\times p 和一个 p\times m 的矩阵。观察规律，我们发现前矩阵的列数需要等于后矩阵的行数。根据如上概括的矩阵乘法的意义——即搭配未知数与系数。显然，当后一个矩阵的列数大于前一个矩阵的行数时，我们进行系数配对时就会发现多出几个失配的系数。矩阵乘法国不养闲人，这种单身汉显然是不可以光天化日下大摇大摆出来遛弯的。因此保证其中一个矩阵的行数等于另一个矩阵的列数后方可相乘。

类比四则运算的乘法，矩阵乘法是否也有结合律、分配律和交换律呢？很遗憾，不完全是，前二者是矩阵乘法运算所具备的性质、但最后那个交换律不是。不是所有的矩阵相乘都满足乘法交换律。但是还是有满足交换律的特例：同型零矩阵相乘、一个矩阵（可逆）和它的逆矩阵相乘，矩阵乘法满足交换律的充要条件证明过于复杂烧脑，此处不做陈述主要是我也不会证满足交换律的充要条件 qwq……。

证明：一般矩阵不满足乘法交换律

假设一般矩阵 A=(a_{np})，一般矩阵 B=(b_{pm})，则 AB 可以进行，因为 A 的行数和 B 的行数均为 p。得到的乘积 C 是一个 m\times m 矩阵；反过来，BA 无法进行，因为 B 的列数不等于 A 的行数，即 m\neq n。

假设 A=(a_{nn}),B=(b_{nn})。AB 和 BA 均可进行，假设乘积为 C=(c_{nn})。当 C=AB 时，根据矩阵乘法的计算式，得到 c_{ij}=\sum\limits_{k=1}^{n}a_{ik}b_{kj}；当 C=BA 时，根据计算公式得 c_{ij}=\sum\limits_{k=1}^{n}b_{ik}a_{kj}。一般情况下，a_{ik}b_{kj}\neq a_{kj}b_{ik}。得证。

矩阵和数字一样，也有幂次方的计算。特殊地，任意 n\times n 非零矩阵的零次幂都是一个 n\times n 的单位矩阵。主对角线的值全是 1，其余元素均为 0 的矩阵叫做单位矩阵，用字母 I 表示；零矩阵的任何非零正整数次幂都是一个零矩阵，零矩阵的元素全部是 0，用字母 O 表示。一个 3\times3 的单位矩阵是这样的：I=\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}。在算法设计中，经常用类似于大数快速幂（位运算版本）的方式快速计算矩阵的幂次方。

例 2.1.1 Akasha Browser with Irminsul Kernel 世界树搜索引擎

你作为刚刚清除了须弥世界树痼疾的英雄旅行者，突然对虚空终端的运作方式有了兴趣。你从大贤者那里了解逼问到，虚空终端实质上是一个仅显示搜索结果的前端程序，但关键词搜索功能却是基于须弥地下空间的世界树。带着这个疑问，你再次来到了世界树前，见到了小吉祥草王大人，希望能让她告诉你世界树的运作方式……

背景知识： 很多浏览器的检索功能都依赖于矩阵运算，这里属于最简单的一种——我们只需要矩阵的乘法运算（某些情况下会用到转置，甚至正交性）。然而随着科技的快步发展，数据量的快速增加，这种方式如今只在很小的范围内被使用（由于码量小思维简单，它有时会在个人博客的关键词搜索功能中被用到）；目前广泛使用的一种是向量相似性搜索，它本质上是在一定范围内搜索与目标向量辐角最为接近的已有向量，在“矩阵的几何表示” 章节中会涉及到。这里介绍的是简单匹配搜索。

问题分析：因为矩阵乘法本质上是未知数和系数的配对求值，我们需要构造一个方法来使得“搜索内容” 和“已有内容” 配对。并且搜索引擎总会返回与你搜索的内容最为相似的结果，搜索“比尔・盖茨”，第一条肯定是关于他个人的介绍，而绝对不可能是一则寻狗启示……因此，我们设计的矩阵必须能在经历一轮运算后能够正确返回每个关键词出现的频率（简单点说就是出现次数），这样虚空终端才能对频率进行排序，并返回频率最大的那个结果。

算法设计：不妨考虑这样几个矩阵 —— 其中一个存储关键词、另一个存储搜索内容。比如我需要将几篇论文（为方便使用英文表示，并且假设词根相同的单词为同一个单词，即不考虑词汇变形）《Basic Structure of Elemental Monuments》（元素方碑的底层构造）、《Junior Elemental Reaction》（初等元素反应）、《Advanced Elemental Theory》（高等元素论）、《Architectural Structure in the Mausoleum of King Deshret》（赤王陵的建筑结构）以及《Advanced Sumeru Linguistic Analysis》（高等须弥语音学解析）。我们在此次挑选一些关键词存储（方便读者观察）：Structure、Element、Junior 和 Advanced。为每篇论文编号 1-5，矩阵如下图：

假如热爱学习的艾尔海森来到了教令院的大图书馆，它想测试一下这全新开发的文献查询系统，输入了 Advanced 一词。假设已录入数据库就是以上形式，我们如何构造一个“查询矩阵” 来和数据库矩阵进行运算呢？

首先根据矩阵乘法的前提要求，这个查询矩阵必须是四行。不妨让每行代表我们的词库词语，艾尔海森输入的是 Advanced—— 即对应数据库矩阵的第四列（未知数），我们要配对它的系数，因此它必须在第四行，才能保证系数正确匹配未知数。同理，查询矩阵的第一行对应 Structure、第二行 Element、第三行 Junior。他输入了一个 Advanced，因此我们的查询矩阵如下图：

乘法的目的是将二者匹配起来，得到的结果如下图：

返回矩阵的数字代表关键词在对应数据库项中的出现次数，也就是说，如果此时再加入一篇论文《Advanced Usage of the Word Advanced》（“Advanced” 一词的进阶用法），返回矩阵的最后一行（第六行）会出现一个 2。经过虚空终端的一轮排序，它自然就会来到第一位的位置。如果要分别查询两个不同关键词，在查询矩阵右侧再加一列即可，返回矩阵中多出的一列就是新关键词的出现次数；如果需要同时查询两个关键词，在同一列对应位置写入 1 即可……

例 2.1.2 Light Novel Query 轻小说查询

八重堂的主编八重神子最近在为轻小说的事情发愁…… 并不是因为销量不够，正相反：八重堂最近推出了一项跨国销售项目，各种经典作品被远销往了枫丹廷。这就牵涉出一个问题 —— 枫丹的市民们不想远离枫丹城区、横穿须弥沙漠、翻越璃月高山、躲避稻妻雷暴就为了看一看有哪些轻小说符合自己的独特口味…… 于是八重神子找到了见多识广的你，希望你能帮她做出一套轻小说内容检索系统。当然作为报酬给你的原石和摩拉是肯定是不会少的……

当然，这套系统有一定要求。因为有很多轻小说为了吸引读者，取的标题和内容是完全对不上号的，神子的想法是做一套正文内容检索 —— 每本轻小说的总字数在出版时就统计好了，但是苦于稻妻的信息存储技术不是很发达，神子希望存储在数据库矩阵里的数据尽可能小。请问该如何设计符合要求的存储算法？

问题分析：每本书中特定的词可能重复出现成百上千次（同样用英文单词表示，且同词根不同词形的两个词算作同一个单词参与计数），我们的要求是让数据尽可能小，既然总字数都已经给出了，我们不妨使用指定词出现的频率来表示这个词的出现次数（单词出现次数 = 全书总词数 × 出现频率）。这样的搜索方法叫做相对频率搜索。

算法设计：大致原理和例 2.1.1 里的一模一样，只是数据库矩阵存储的不再是出现总次数，而是对应词的相对频率。因而图例 2.1.3 可以变化为如下形式：

明显一看，第三篇文章出现 Advanced 的频率最高，应该优先返回。但是这个例子并不是很好（明明说了按内容搜索你还在这搜索标题），但是当加入大量的正文内容时，这个方法的优势也就体现出来了。这里由于篇幅原因就不举过于复杂的例子，本例仅作对相对频率搜索的原理的理解。

第二节 初等矩阵与矩阵递推

假设存在一个 n\times n 的单位矩阵 I，对 I 只进行一次初等行变换得到的矩阵叫做初等矩阵，通常用 E 表示。一个矩阵的行变换和列变换都可以用初等矩阵的乘法进行。

仅交换了两行的单位矩阵称作第 I 类初等矩阵（只进行了初等行变换第一条），将它左乘到一个矩阵前，可以进行相应的行运算；右乘到一个矩阵后可以进行相应的列运算。比如，一个第 I 类初等矩阵 E_I=\begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{bmatrix}（交换第一、二行），和一个 3\times3 矩阵 A=\begin{bmatrix} 4 & 2 & 5\\ 0 & 2 & 6\\ 5 & 5 & 1\end{bmatrix}。左乘就是 E_IA=\begin{bmatrix}0 & 2 & 6 \\ 4 & 2 & 5\\ 5 & 5 & 1\end{bmatrix}（交换一、二行）；右乘就是 AE_I=\begin{bmatrix} 2 & 4 & 5\\ 2 & 0 & 6\\ 5 & 5 & 1\end{bmatrix}（交换一、二列）。

仅将某一行乘以一个非零倍数的矩阵叫做第 II 类初等矩阵（只进行了初等行变换第二条），左乘行运算、右乘列运算。例如一个第 II 类初等矩阵 E_{II}=\begin{bmatrix} 3 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}（第一行乘 3）和一个 3\times3 矩阵 A=\begin{bmatrix} 4 & 2 & 5\\ 0 & 2 & 6\\ 5 & 5 & 1\end{bmatrix}。E_{II}A=\begin{bmatrix} 12 & 6 & 15\\ 0 & 2 & 6\\ 5 & 5 & 1\end{bmatrix}（第一行乘 3）；AE_{II}=\begin{bmatrix} 12 & 2 & 5\\ 0 & 2 & 6\\ 15 & 5 & 1\end{bmatrix}（第一列乘 3）。

仅将某一行的非零倍加到另一行上的矩阵叫做第 III 类初等矩阵（只进行了初等行变换第三条），同样是左乘行运算、右乘列运算，但是有一点点小不同，不要根据思维定势随便写答案！例如一个第 III 类初等矩阵 E_{III}=\begin{bmatrix} 1 & 2 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\end{bmatrix}（第二行乘 2 加到第一行）和祖传的矩阵 A=\begin{bmatrix} 4 & 2 & 5\\ 0 & 2 & 6\\ 5 & 5 & 1\end{bmatrix}。E_{III}A=\begin{bmatrix} 4 & 6 & 17\\ 0 & 2 & 6\\ 5 & 5 & 1\end{bmatrix}（第二行的 2 倍加到第一行）；AE_{III}=A=\begin{bmatrix} 4 & 10 & 5\\ 0 & 2 & 6\\ 5 & 15 & 1\end{bmatrix}（第一列的 2 倍加到第二列）。注意初等矩阵的行列变换与乘法后矩阵的行列变换，哪一行/列乘了倍数、哪一行/列被加上了！

因此我们可以不必使用高斯消元，仅使用初等矩阵乘法也可以达到将普通矩阵消元变成最简行阶梯形矩阵！而且它可以进行列运算，甚至比高斯消元法更高级一点。

接下来是我们的矩阵递推。大家都知道斐波那契数列，它的前两项均为 1，此后的每一项都是前两项之和，即 a_n=\begin{cases}a_{n-1}+a_{n-2}&n>2\\1&n=1,n=2\end{cases}。大多数信息竞赛生在学习到递归算法时都会被要求写程序求解斐波那契数列的某一项，当然代码也非常的简单，如下：

#include <bits/stdc++.h>
using namespace std;

long long fib(int n)
{
    if (n == 1 || n == 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

int main()
{
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

这段代码其实就是照搬了上面的通项公式，但是递归有个弊端就是效率和内存，当 n 为百万级别、甚至十亿级别时它就显得很小丑了。那么我们如何用矩阵加速计算呢？我们用斐波那契数列的递推来向读者介绍矩阵递推的操作方法：

首先我们将通项公式变成我们想要求的形式，为了便于输出，要求结果矩阵的第一个元素就是答案，因此结果矩阵就是：\vec a=(a_n,a_{n+1})。又因为 a_n=a_{n-1}+a_{n-2}，并且 a_{n+1}=a_n+a_{n-1}。我们还需要保证初始矩阵在经历一轮变换前后，始终都是同型的，这里是 1\times2 的矩阵，操作后也应该是 1\times2 的矩阵。于是我们的递推矩阵应该是一个 2\times2 矩阵。不妨将递推矩阵 M 的每一行从上至下分别表示为 a_{n-1} 和 a_{n-2} 的系数，由以上二式可得：M=\begin{bmatrix} ? & 1 \\ ? & 1\end{bmatrix}。别急，左边还有一列未填满 —— 我们希望每次操作都会把矩阵元素整体向左移一个位置，就好像一个滑动窗口（但不是单调队列），我们的第一列也可以求出来了。最终就是 M=\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}

那么求数列第 n 项 —— 每次右乘 M 都相当于多求出一项，并且当 M 只被乘了一次时，结果矩阵的第一个元素是 a_2。因此要让第 n 项来到第一个位置，我们需要进行 n-1 次乘法，a_n 也就是 AM^{n-1} 的第一行第一列元素。可以写出如下代码：

#include <bits/stdc++.h>
#define MOD 1000000007
#define N 15
using namespace std;

typedef long long ll;

int n = 2; // 递推矩阵行列数均为2

struct Matrix {
    ll mat[N][N];

    Matrix()
    {
        memset(mat, 0.0, sizeof mat); // 初始化时内部变量自动置零，无需每次定义变量时再置零
    }

    void I()
    {
        for (int i = 1; i <= n; i++)
            mat[i][i] = 1; // 构造2×2单位矩阵
    }
};

Matrix operator*(const Matrix& l, const Matrix& r)
{
    // 重载乘法运算符，实现矩阵乘法
    Matrix res;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // res.mat[i][j] = (res.mat[i][j] + l.mat[i][k] * r.mat[k][j] % MOD) % MOD; // 取模用这个
                res.mat[i][j] += l.mat[i][k] * r.mat[k][j];
            }
        }
    }
    return res;
}

Matrix qpow(Matrix a, ll b)
{
    Matrix res;
    res.I(); // 单位矩阵相当于实数运算中的 1，因此任何矩阵乘以一个单位矩阵的结果都是这个矩阵
    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main()
{
    int a;
    cin >> a;

    Matrix A;
    A.mat[1][1] = A.mat[1][2] = 1; // 初始矩阵
    Matrix M;
    M.mat[1][2] = M.mat[2][2] = M.mat[2][1] = 1; // 递推矩阵
    A = A * qpow(M, a - 1);
    cout << A.mat[1][1] << endl;
    return 0;
}

它的时间复杂度可以做到 \mathcal O(n^3\log T)，n 是 M 的长/宽，这里是 2；T 是幂。因此这里的时间复杂度是矩阵快速幂的 \mathcal O(\log T)，比朴素斐波那契递推的 \mathcal O(2^{T-1}) 强了不少！

例 2.2.1 Lost Control! Blubberbeast's Reproduction 膨膨兽泛滥危机

由于枫丹水质的大幅改善，膨膨兽的天敌数量锐减，枫丹城区近海的膨膨兽也得到了更多的食物，进而开始大量地繁殖。水质改善的第一年，已登记的膨膨兽数量是 6765 头，恰好是斐波那契数列的第 20 项。第二年，膨膨兽数量没有变化，之后的每一年，膨膨兽数量都是前两年之和的 85\%，已知膨膨兽的平均寿命是 15 年、枫丹廷近海能承载的最大膨膨兽数量是 90 万只。那么请问 15 年后近海的膨膨兽数量是多少？这 15 年内枫丹廷是否需要向近海投放膨膨兽的天敌以遏制后者疯狂繁殖？（结果出现出现小数则向上取整）

问题分析：这是一道标准的矩阵快速幂递推问题，它基于斐波那契数列递推、却比它更高级。首先，它的初始值不再是 (1,1) 而是 (6765,6765)，其次，从第三项起，每一项都是前两项和的一个倍数，这里是 0.85。那我们怎么构造递推矩阵 M 来解决问题呢？

算法设计： 已知初始矩阵 A=(6765,6765)。根据题目描述很容易写出通项公式：a_n=\begin{cases}6765&0<n\leq2\\0.85(a_{n-1}+a_{n-2})&n>2\end{cases}。我们要保证初始矩阵经过一次递推后，得到的新矩阵与初始矩阵同型，因此根据矩阵乘法定义，我们的递推矩阵必须是一个 2\times2 矩阵。于是拿出祖传单位矩阵模板 I=\begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} 开始构造递推矩阵！

对于前项和的问题，前面已经给出了，因而我们的递推矩阵变成了 M=\begin{bmatrix} 0 & 1 \\ 1 & 1\end{bmatrix}；接下来解决倍数问题 —— 根据通项公式，a_{n-1} 和 a_{n-2} 的系数都是 0.85，我们构造递推矩阵时也要考虑到这一点，当 n>2 时，递推公式展开如下：a_n=0.85a_{n-1}+0.85a_{n-2},a_{n+1}=0.85a_n+0.85a_{n-1}。如果第一行代表 a_{n-1} 的系数、第二行代表 a_{n-2} 的系数 0.85，第二列显然应该同时乘以 0.85，左边一列的作用是使原矩阵整体向左移一个位置。最后我们的递推矩阵就是 M=\begin{bmatrix} 0 & 0.85 \\ 1 & 0.85\end{bmatrix}。直接将初始矩阵右端乘以递推矩阵的幂次方就可以了。注意因为初始矩阵的右侧是第二年的膨膨兽个数，乘以递推矩阵本身，会让第二年的膨膨兽个数移到结果矩阵的前端，要想让第一项变成第 15 年的个数，递推矩阵的幂必须是 14，即 15-1。

代码实现上，仅需将 A 矩阵和 M 矩阵的初始值改变就可以了。

最终结果：875076。结果小于 90 万，因此不需要投放天敌。

后日谈：那如果将系数改变为 0.86 呢？输出的结果将是 977427，接近 100 万了。可见其增长速度之恐怖。

洛谷例题：

1. P3390 [模板] 矩阵快速幂
2. P1962 斐波那契数列
3. P1349 广义斐波那契数列
4. P1939 矩阵加速（数列）
5. P3216 [HNOI2011] 数学作业

第三章 矩阵的逆

第一节 浅谈矩阵的逆

“逆” 这个词相信你早已听说过：同余意义下存在乘法逆元，大多数矩阵也存在逆矩阵。“逆” 普遍用来描述不同意义下的“倒数” 的概念，倒数一般满足 a\cdot a^{-1}=1 的性质，即本体 × 本体的逆 = 单位一。矩阵中的“单位一” 是单位矩阵 I，也因此我们的逆矩阵需要满足这个式子：AA^{-1}=I，并且这个式子倒过来也必须成立（为数不多的满足矩阵乘法交换律的情况之一）。

如果对于一个矩阵 A，存在另一个矩阵 B，使得：AB=BA=I 成立。则称矩阵 A 是可逆的，或称之为非奇异的，矩阵 B 是矩阵 A 的逆矩阵，通常表示成 A^{-1}。特殊地，单位矩阵 I 的逆矩阵是它本身，即 II=I^2=I；零矩阵 O 不可逆，或称之为奇异的，即不可能存在矩阵 B，使得 OB=BO=I。

这一点类比实数运算：1 的倒数永远是它本身、0 没有倒数，因为分母为 0，没有意义；2\times0.5=0.5\times2=1，同时 0.5=2^{-1}。

第二节 行列式

行列式是一种函数，写出来有点像矩阵的绝对值。它可以用来判断一个矩阵是否有解、也可以定量分析线性变换对原向量的影响。矩阵 A 的行列式通常用 \det(A) 或者是 |A| 表示。这一节主要介绍行列式判断矩阵是否可逆。同时，行列式也可以用来判断方程组是否有解。

定义 2\times2 矩阵 A=\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix} 的行列式为 \det(A)=a_{11}a_{22}-a_{12}a_{21}。特殊地，1\times1 矩阵的行列式就是 a_{11} 的值。当一个矩阵的行列式为 0 时，它是奇异的、也就是不可逆的；反之则非奇异/可逆。

那我们在上边只提到了两种尺寸的方阵，那对于 3\times3、4\times4、以至于 n\times n 的方阵又该怎么办呢？答案是分而治之——分治！

第三节 代数余子式展开/\texttt{Laplace} 展开

我们拿出祖传的 3\times3 矩阵 A=\begin{bmatrix} 4 & 2 & 5\\ 0 & 2 & 6\\ 5 & 5 & 1\end{bmatrix}，我们随机在其中挑选一位受害者。我个人看第二行第一列的 0 元素不太顺眼，作为矩阵 A 的定义者，我有权利将它变成自己所喜欢的样子，因此我把元素 a_{21} 拿掉。可是拿掉以后它还是个 0！于是我将它所在的那一行以及那一列全部剔除，把剩下的元素按照原来的相对顺序靠拢，组成一个新的 2\times2 矩阵 B=\begin{bmatrix}2&5\\5&1\end{bmatrix}。现在整个矩阵没有 0 元素了，看上去清爽多了。

像上边这样，将 n 阶行列式中元素 a_{ij}（1\leq i\leq n,1\leq j\leq n）所在的第 i 行、第 j 列所有元素删去，剩下元素组成的新 n-1 阶行列式叫做原行列式的余子式，用 M_{ij} 表示。

在矩阵运算中，Ax=0 的零解 x=0 就是这个方程的一个平凡解。（因为实在是太显而易见了所以很平凡）

证明：首先证第一条可以导出第二条。假设 A 为非奇异方阵，x^\prime=0 是方程的一个解。因此 x^\prime=Ix^\prime=(AA^{-1})x^\prime=A^{-1}(Ax^\prime)。因为 x^\prime 是 Ax=0 的一个解，因此 Ax^\prime=0，原式 =A^{-1}(Ax^\prime)=A^{-1}\cdot0=0。因而原方程仅有平凡解。

再证第二条可以导出第三条。A 可以化简成行阶梯形矩阵 U，方程变为 Ux=0。因为严格三角形矩阵可以通过变换得到单位矩阵 I，所以需要证明 U 是否是严格三角形矩阵。如果 U 的主对角线出现了 0，那肯定不是严格三角形矩阵。因为阶梯形矩阵要保证每一行都比它的上一行前边的 0 元素多，因为 A 是方阵，到最后一行时只能全部为 0。此时矩阵有无数组解，因为实际上他只列出了 n-1 个方程，最后一行的方程不被计入系数矩阵和增广矩阵的秩，导致 R(A)=R(B)<n。因此有无数组解；反之若 U 的主对角线全不为 0，它可以被化简成单位矩阵 I（使用高斯消元即可）。因此 A 与 U 行等价、U 与 I 行等价，传递得 A 与 I 行等价。

最后证第三条可以导出第一条。根据行等价的定义，必有 I=E_1E_2E_3\dots E_{k-1}E_{k}A。根据方才证明的结论：初等矩阵是非奇异的，根据单位矩阵的性质：单位矩阵也是非奇异的。因而 A 也是非奇异的，且 A^{-1}=(E_1E_2\dots E_{k-1}E_k)^{-1}=E_kE_{k-1}\dots E_2E_1。得证。

根据第三条，我们就可以知道一个求逆矩阵的方法了：既然 I=E_1E_2E_3\dots E_{k-1}E_{k}A，我们给等号两端同时乘一个 A^{-1}，得到 A^{-1}=E_1E_2E_3\dots E_{k-1}E_{k}I。因此 A^{-1} 又与 I 行等价。前两个方程是一对等价方程，我们换元，假设 x=E_1E_2E_3\dots E_{k-1}E_{k}，两个方程如下：\begin{cases}I=xA\\A^{-1}=xI\end{cases}。因此增广矩阵 (A|I) 可以被化简为 (I|A^{-1})。我们只需高斯消元将分隔线左侧化成 I，右侧自然就是逆矩阵 A^{-1} 了。

例 3.4.1 How Aranaras Measure Timeflow 兰那罗的时间观念

你在须弥冒险时，遇到了森林可爱的孩子们 —— 兰那罗。这些小小的生物有着与世无争的纯净心灵、以及大大的胸怀。你们一同冒险，击败了桓那兰那故土的污秽化身，拯救了须弥森林。然而，在和兰那罗对话期间，除开他们奇妙的比喻之外，还有一件事情是你久久无法忘怀的 —— 他们的时间单位。你听过最多的是“种子长成大树”、“太阳升起又落下”、“落落梅从出生到长大”、“大树长成雨林”……

假如你们经过很长一段时间的交谈，你渐渐明确了各种时间描述词之间的数学关系，关系如下文所述。请你求出每个描述词所对应的时间间隔。

1. 已知大树长成雨林的时间是种子长成大树的 50 倍。
2. 树木从种子长成大树的期间，落落莓已经生长过整整 15 次了（由种子出生到果实成熟和从成熟到下一颗种子扎根生长的时间相同）。
3. 兰那罗从种子长成大树期间，普通人已从黑发少年变为白发苍苍的老人了。
4. 普通人从青年到老年的时间足够让三颗种子先后成长为大树。
5. 一片树木生长成为雨林，不仅足够让 16 个人先后从少年变为老年，而且还需要额外的 60 年时间完全长成一片健康的雨林。

请问“大树长成雨林”、“树木从种子长成大树”、“兰那罗从种子变成大树”、“落落莓从扎根到成熟” 以及“普通人从少年到老年” 所经过的时间各是多少年？（四舍五入到最近整数，单位：年）

问题分析：既然各个描述词对应时长的倍数关系都已给出，我们可以两两列出方程组求解。这里我们用到矩阵的逆来方便求出方程的解。

算法设计：首先将各个描述词用未知数表示出来，再用数学关系表示出题干中各个描述词的关系，如此得到的 5 个方程恰好能使矩阵有唯一解。因为一般的方程 Ax=b 可以写成 x=A^{-1}b 的形式，所以求出 A 的逆矩阵，再对常数项组成的列向量进行左乘即可。

解：设“大树长成雨林”、“树木从种子长成大树”、“兰那罗从种子变成大树”、“落落莓从扎根到成熟” 以及“普通人从少年到老年” 的时间分别为 x_1,x_2,x_3,x_4,x_5 年。根据题干描述。可以得到如下关系：

整理得：

对应系数矩阵 A=\begin{bmatrix}1&-50&0&0&0\\0&-1&0&30&0\\0&0&1&0&-1\\0&-3&0&0&1\\1&0&0&0&-16\end{bmatrix}。常数矩阵 b=\begin{bmatrix}0\\0\\0\\0\\60\end{bmatrix}，未知数矩阵 x=\begin{bmatrix}x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix}。对应方程为 Ax=b。

两侧同时乘以 A^{-1} 得：x=A^{-1}b。根据逆矩阵求法，初始矩阵为：

高斯消元后，将 (A|I) 消成 (I|A^{-1}) 形式，得：

第六节 行列式在高中数学中的应用

这一节的内容是 2024 年 11 月份新加入的。是适合高中生体质的快速解题技巧。

一. 向量叉乘/平行四边形面积

例题详见：2024 年新高考一卷 T16。

高中立体几何学了向量数量积/点乘，定义如下：

\vec a\cdot\vec b=|\vec a||\vec b|\cos\theta

其中 \theta 是两向量间的夹角。结果为标量（实数）。

类比点乘，我们定义叉乘为：

模长为 |\vec a||\vec b|\sin\theta，方向与参与运算的所有向量垂直的向量。

观察到这个模长很像正弦定理中三角形面积公式 S_\triangle=\frac{1}{2}ab\sin\theta。事实上，这个结果代表两向量围成的平行四边形面积，因此 S_\triangle=\frac{1}{2}\vec a\times\vec b。那我们怎么去计算这个结果呢？有人会说：“那不是还要算 \sin\theta，更麻烦了吗？”

联想到本节标题，其实二维向量叉乘是可以用 2\times2 方阵的行列式来算的。把三角形的两边用向量表示出来组成一个方阵 A=\begin{bmatrix}x_1&y_1\\x_2&y_2\end{bmatrix}，于是 |\vec a\times\vec b|=|\det(A)|=|x_1y_2-x_2y_1|。

不到万不得已，考试时千万别用这一招，如果一定要用，请一定记住写出下面的证明过程才能保证不扣分或者扣分少一点。

证明：

从 \sin\theta 的计算方法 |\sin\theta|=\sqrt{1-\cos^2\theta} 开始，三角形中 \theta\in(0,\pi)（注意区间表示实数，不能写作 \theta\in(0\degree,180\degree)），得出 1>\sin\theta>0。

那么：

此时将坐标 \vec a=(x_1,y_1),\vec b=(x_2,y_2) 代入得：

得证。

做题时又会发现，围成三角形的是两个三维空间向量，难道要用 2\times3 矩阵求行列式吗？

答案是否定的，事实上我们可以想办法把它补充成一个完整的 3\times3 方阵。具体来说就是在第一行加入这个三维空间的基底向量，然后稍作变化。例如求解 \vec a=(1,2,6) 和 \vec b=(2,-1,3) 围成的三角形面积：

我们可以加入基底向量 \vec c=(1,1,1)，或者一般地，\vec c=(i,j,k)，然后组合成矩阵：

2. (\bold x+\bold y)+\bold z=\bold x+(\bold y+\bold z)
3. \bold x+\vec0=\bold x
4. \bold x+(-\bold x)=\vec 0
5. \alpha(\bold x+\bold y)=\alpha\bold x+\alpha\bold y
6. (\alpha+\beta)\bold x=\alpha\bold x+\beta\bold y
7. (\alpha\beta)\bold x=\alpha(\beta\bold x)
8. 1\cdot\bold x=\bold x

好多啊 ccc，其实就是需要把“加法” 定义成正统的加法（满足交换律、结合律）；“数乘” 定义为正规的数乘（满足结合律、分配律，没有交换律）。可以发现矩阵的加法和数乘和它完美匹配！因此矩阵可以作为一个向量空间。

于是，向量空间 V 中的元素称作向量。因为这个空间需要包罗万象，就像宇宙空间要包含我们赖以生存的地球一样……它包括我们所需要的向量，因此向量运算最基本的两种——加法与数乘运算所导出的结果必须也在向量空间 V 内，这叫做向量空间内加法和数乘的封闭性，向量空间必定符合这个性质。如此一来，向量空间 V 就足以作为向量所生存的“宇宙空间” 了。

当然有时我们并不需要那么多空间，好比一个人住一个城市……先不提城市各项环节能否正常运作，如果只是用来溜达的，那也是太过巨大了，有些地方可能你一辈子也取不到，还不如开始就不要。向量空间其实也可以像这样压缩范围，并且压缩后的向量空间也必须是全集 V 的子集。根据向量空间的定义，该空间内的向量做任意加法和数乘运算得到的结果都得是空间内的向量。

若向量空间 V 的子集 S 满足加法和数乘运算的封闭性，那么 S 是 V 的一个子空间。特殊地，\{\bold 0\} 与 V 都是 V 的子空间，\{\bold0\} 称作零子空间，其他非零且不等于 V 的子空间称作真子空间（类比集合的空集、子集和真子集概念）。

在矩阵中，也存在零空间。它表现为矩阵方程 Ax=\bold0 在 \bold R^n 上的解集 N。我们首先验证数乘封闭性，A\alpha x=\alpha(Ax)=\alpha\cdot\bold0=\bold0\in N；紧接着是加法封闭性：A(\bold x+\bold y)=A\bold x+A\bold y=\bold0+\bold0=\bold0\in N。封闭性得证，因此 N 是 A 的子空间。这种空间被称作矩阵的零空间，通常用 N(A) 表示 A 的零空间。

例 4.1.1 Merusea Village Portal 海露村传送门

自从你来到枫丹，知晓了水仙十字结社的秘密之后，奇怪的事情开始在你身边上演……

你在海露村遇见了抽象派美露莘大画师玛梅赫、以及一只发条机关狗西摩尔。很不巧，玛梅赫的作画颜料用完了，于是你们前去收集更加纯净的矿物颜料，期间玛梅赫邀请你们进入一个粉色的漩涡虫洞。或许是因为你前一天冒险到深夜，在这个温暖且舒适的环境下来了困意。一闭眼，再一睁眼，迎接你的不是如同往常一般的新地下区域 —— 而是一片温暖的、舒适的粉色幻境 —— 你被一个人丢在这个传送通道里了！

为了不让派蒙着急，同时也为了你能尽快在下一次困意席卷前逃出这个空间，你需要确定这个传送门是否为“同维度空间卷曲型”—— 即传送过程中不发生维度的变化。你需要证明你身处的空间是一个三维空间的子空间，这样才能使用正确的方法逃出生天。你发现你的身高和体宽的比值是原来的一半、但是体宽不变。请证明你所在的空间是是三维空间的子空间。

问题分析：首先要根据已有的信息判断该向量空间是否为三维向量空间的子集，然后再验证加法与数乘的封闭性，只有当二者均成立时才能够证明该空间是三维空间的子空间。

算法设计：根据题干最后一句话，我们不妨将主人公设为三维坐标系原点，按照 x,y,z 三个坐标轴来建立变换关系。比如说“身高体宽比减半” 代表的是现在的 z 轴是 x 轴的一半，假设原身高在 z 轴上有 4 个单位，而现在只有两个单位，证明现在的 z 轴被拉伸了一倍。最后关于封闭性的证明，设出几个具有普遍性的向量证明即可。

解：根据变换关系，得到该向量空间的集合形式 S=\left\{\begin{bmatrix}x\\y\\z\end{bmatrix}|z=\frac{1}{2}x\right\}。因此 S 为 \bold R^3 的子集，令 x=\begin{bmatrix}2x\\2y\\y\end{bmatrix}， 数乘：\alpha x=\begin{bmatrix}2\alpha x\\2\alpha y\\\alpha y\end{bmatrix}\in S；令 a=\begin{bmatrix}2a_x\\2a_y\\a_z\end{bmatrix}，b=\begin{bmatrix}2b_x\\2b_y\\b_z\end{bmatrix}，a+b=\begin{bmatrix}2(a_x+b_x)\\2(a_y+b_y)\\a_z+b_z\end{bmatrix}\in S，封闭性得证。

因此，所在空间 S 是三维空间的一个子空间。

第二节 基底、张成与张集

假设 \bold R^n 中有向量 v_1,v_2,v_3\dots v_n，那么 \alpha_1v_1+\alpha_2v_2+\alpha_3v_3+\dots+\alpha_nv_n 称作向量 v_1,v_2,v_3\dots v_n 的线性组合。向量 v_1,v_2\dots v_n 的所有线性组合构成的集合叫向量 v_1,v_2\dots v_n 的张成。

我们都知道，n 个不共线向量唯一确定一个 n 维平面。假如有向量：\vec a=\left[\begin{array}{ccc}1&1&3\end{array}\right]^T 和 \vec b=\left[\begin{array}{ccc}-1&2&-1\end{array}\right]^T。它们的张成就是（注：最好是验证两个向量在三维空间里的张成，既直观还符合常规认知）它们围成的 n 维平面。方才的 \vec a 和 \vec b 的张成如下图：

如果 \alpha_1v_1+\alpha_2v_2+\alpha_3v_3+\dots+\alpha_nv_n=V，则称 v_1,v_2\dots v_n 张成 V。用 Span(v_1,v_2,\dots,v_n) 表示。有以下两条性质：

1. 若 v_1,v_2,\dots,v_n\in V，则 Span(v_1,v_2,\dots,v_n) 为 V 的子空间
2. 向量平面 V 中一组向量的张成是 V 中包含这组向量的最小子空间

对于第一条，因为你怎么拟合平面，都不可能让你的平面比整个空间的维度更高，而且无论以什么系数搭配向量，它们所得的新向量都在整体空间内，第一条就能很简明的证明了。第二条性质，首先空间内向量的张成必为整个空间的子空间，毕竟用的都是数乘和加法，用的向量也都在空间内，总不能算一下加法向量就跑到空间外边去了吧，此外，因为数乘和加法的封闭性，任何经过这两个向量的空间都包含其张成，因此它是最小的。

l和张成相对，如果 v_1,v_2\dots v_n 张成 V，则 V 是 v_1,v_2\dots v_n 的张集。

基底，大家在高中立体几何部分学过了。当时的定义是：平面内不共线的两个向量叫做这个平面的一组基底。然而这段话可以用线性代数的语言原原本本描述出来：

在 n 维向量空间 V 中有 n 个线性无关的向量 v_1,v_2,\dots,v_n，则称它们是向量空间的一组基。

线性无关的概念，之前已经简单讲过，总的来说就是向量不共线，即不存在标量 \alpha\in\mathbb R，使得 \alpha v_1=v_2；线性相关则反之，指的是两个向量共线，即 \exists\alpha\in\mathbb R,\alpha v_1=v_2 成立。正如在高中课堂上学的一样，给出一个 n 维空间的一组基底，该空间上所有的向量都可以用这组基底唯一地表示出来。比如下边这个例子：

例 4.2.1 Al-Ahmar's Test 赤王的试炼

你和婕德一行人在圣显厅前击败了图谋不轨的镀金旅团，并在他们搭起的营帐里发现了一封密信。上面写着若想进入圣显厅，需先过三关试炼。为了能够一探黄金梦乡的秘密，你接下了完成三重试炼的任务，然而当你真正进入到第一重试炼时，却发现事情并没有这么简单……

你进入了试炼场地，却发现整个世界天旋地转。最终安定下来，你发现赤王的神奇科技把你带入了一个 n 维空间内。这还没完，四周又有整齐排列的空气墙阻挡了你的通路。经过好一顿摸索，你终于发现这是一个 5 维空间，于是你开始建立空间坐标系，五个坐标轴分别是 w,x,y,z,t，假设你现在所在的地方是原点 O(0,0,0,0,0)，通关点 P(4,2,-1,3,0)。四周的空气墙限制了你仅能沿着与向量 \vec a=(2,2,0,1,3),\vec b=(-1,0,3,1,5),\vec c=(-2,0,0,4,1),\vec d=(1,1,2,6,7),\vec e=(1,1,2,2,6) 平行的方向行动。请问如何安排前进方向使得你能够从起点 O 到达终点 P？

问题分析：这个问题明显是让我们用 \vec a,\vec b,\dots,\vec e 来表示出从起点（原点）到终点的一个向量，因为这五个向量不共线，可以作为五维向量空间的一组基底。又因为基底可以唯一地表示出平面上的所有向量，考虑列方程组求解每个基向量的系数关系。

解：明显地，题中五个向量互相线性无关，因此可以作为该平面的一组基。由于向量加法和数乘运算的封闭性，且路径向量 \vec p=(4,2,-1,3,0) 在该平面上，因此可以拆分成这些基向量的倍数和形式。

设 \vec p=\alpha_1\vec a+\alpha_2\vec b+\alpha_3\vec c+\alpha_4\vec d+\alpha_5\vec e，则有方程组 \begin{cases}2\alpha_1-\alpha_2-2\alpha_3+\alpha_4+\alpha_5=4\\2\alpha_1+\alpha_4+\alpha_5=2\\3\alpha_2+2\alpha_4+2\alpha_5=-1\\\alpha_1+\alpha_2+4\alpha_3+6\alpha_4+2\alpha_5=3\\3\alpha_1+5\alpha_2+\alpha_3+7\alpha_4+6\alpha_5=0\end{cases}，方程组的解：\begin{cases}\alpha_1=2\\\alpha_2=1\\\alpha_3=-1.5\\\alpha_4=2.5\\\alpha_5=-4.5\end{cases}

因此，应在 \vec a 方向上移动 2|\vec a|，在 \vec b 方向上移动 |\vec b|，在 \vec c 的反方向上移动 1.5|\vec c|，在 \vec d 方向上移动 2.5|\vec d|，在 \vec e 的反方向上移动 4.5|\vec e| 就可以到达终点。

因此一旦选定了平面的基底，该平面上所有的向量都可以用这组基底唯一表示出来，具体操作是使待求向量 u=\alpha_1v_1+\alpha_2v_2+\alpha_3v_3+\dots+\alpha_nv_n，接着解方程求出系数 \alpha 的值即可。在高中，我们称之为“待定系数法”。

基底可以表示平面内所有的向量，故 n 维平面 V 的基张成 V。

第三节 线性基

第二节里我们讲了向量空间的基底，基底其实还有一个名称叫线性基。平面中所有向量唯一对应一种基底的线性组合。在 OI 中常常被用于求第 k 大异或和的问题。为了和实数四则运算的线性基区分，这种线性基下称异或线性基。此节针对于 OI 算法，因此本节所述的“线性基”均默认为“异或线性基”。

一组值的异或和可以看做该空间内异或线性基的向量的异或组合，由于基底表示向量的唯一性：原集合中的数可以通过异或线性基里的基向量唯一确定。它有如下几个性质，事实上，它和普通平面内的实数线性基有相似之处：

1. 原序列中任何元素都可以通过异或线性基内的元素异或得到
2. 异或线性基不存在重复元素，且在保证性质一的前提下，它的元素最少

异或运算也有一个特殊性质，若 a\;xor\;b=c，则 a=c\;xor\;b

根据以上性质构造计算方法：

void insert(ll x)
{
    for (int i = 63; i >= 0; i--) {
        if ((x >> i) & 1) { // 要存放的数的当前位为1
            if (!p[i]) {
                p[i] = x; // 异或线性基该位为0，二进制下该位置为1
                break; // 已找到位置存放，退出循环
            }
            x ^= p[i]; //  异或线性基该位为1，为化为下三角形矩阵形式方便计算置为0
        }
    }
}

由于一般题目中数据范围是 1e18，而转换为二进制位就有 \log_210^{18}=18\log_210\approx60 位，因此数据类型最好选用无符号长长整型 unsigned long long，线性基 p 数组至少需要 60 位。

有时并不是所有的插入操作都会成功，因为要保证异或线性基里的向量互相线性无关。存储操作本质上是拆分二进制位，然后将它尽量表示为已有基向量的异或和，好像除去每个人身上的共同特征，只保留人的独特个性一般。如果拆到最后再也拆不了了，证明它是独特的，可以加入其中。反之，这个数就可以被其他数通过异或运算代替，没必要加它，返回插入失败。可以有下面的代码：

bool insert(ll x)
{
    for (int i = 63; i >= 0; i--) {
        if ((x >> i) & 1) {
            if (!p[i]) {
                p[i] = x; // 异或线性基该位为0，二进制下该位置为1
                break; // 已找到位置存放，退出循环
            }
            x ^= p[i]; //  异或线性基该位为1，为化为下三角形矩阵形式方便计算置为0
        }
    }
    return x; // 若被异或分解为0，则证明它可以被现有元素计算得到，为保证异或线性基元素互相线性无关，不予插入
}

如果是求一个数能否被这个异或线性基表示出来，将最后一行改为 return !x; 即可（能表示即不可插入，不能表示即可以插入）。若某次插入失败，证明 \bold 0 可以被表示出来，在求最小值是要额外关注！我们在此维护一个布尔值 flag = false，在插入失败后设为 true 表示需要特判 0。

线性基用于求解一组数的异或和最值问题，有下面求最值的三个例子。它们无一例外使用了贪心法：

一. 求最大值

ll xorMax()
{
    ll ans = 0;
    for (int i = 63; i >= 0; i--) {
        ans = max(ans, ans ^ p[i]);
    }
    return ans;
}

为什么从高位开始遍历？我们都知道如果一个数字的某位数大于另一个数字相同位置的数（两数数量级相同，即十进制下位数相同），那么前者是大于后者的。根据异或的运算法则：“不同为 1，相同为 0”。如果 ans 的高位此时是 0，若进行异或运算的同位数字是 0，即二者相同，结果为 0，不会变得更小；反之若异或运算的对应二进制位为 1，当前位异或结果是 1，变大了，因此 \text{ans}\;xor\;p_{i}\geq\text{ans}；如果 ans 高位为 1，运算数对应位为 0，结果为 1，不会变得更大；若运算数当前位是 1 异或结果为 0，变小了，所以 \text{ans}\;xor\;p_{i}\leq\text{ans}。

二. 求最小值

ll xorMin()
{
    ll ans = 0;
    if (flag)
        return 0; // 特判0
    for (int i = 0; i <= 63; i++) {
        if (p[i])
            return p[i];
    }
}

我们知道，可以通过任意组合（异或运算）异或线性基中的元素来得出各种新的元素，若 \bold 0 无法被表示出来，我们找到异或线性基里最小的元素即可，因为异或线性基里的每个元素也是原序列中某些元素的异或和；反之返回 0。

三. 求第 k 小值

这才是异或线性基的高级玩法

为了求第 k 小值，首先要对异或线性基进行一轮清扫。将它高斯消元化简为最简形式，称作重构 rebuild。

void rebuild()
{
    for (int i = 63; i >= 0; i--) { // 从高位开始按位扫
        for (int j = i - 1; j >= 0; j--) { // 遍历右移
            if ((p[i] >> j) & 1)
                p[i] ^= p[j]; // 保证p[i]是异或线性基里第i位最小的那个，通过不断异或可以变小
        }
    }
}

接着我们需要特判 0，如果每一次插入都可以成功进行，向量之间互相线性无关，也就无法表示 \bold 0。在求 k 小值时，若 k=1，也就是说求最小值，明显应该返回 0，如果按照常规思路返回 f(k) 就是错误的，因为这个做法的前提是 f(1)\neq0。所以如果先前的插入操作出现失败的情况，就要对 0 进行特判，原先的 f(k) 实为 f(k-1)：

ll queryKMax(ll k)
{
    if (k == 1 && flag)
        return 0; // 特判
    if (flag)
        k--; // 特判0，f(k)实为f(k-1)
    rebuild(); // 重构异或线性基
    ll ans = 0;
    for (int i = 63; i >= 0; i--) {
        if (p[i]) {
            // 对k进行二进制分解
            if (k & 1)
                ans ^= p[i]; // 位为1，异或
            k >>= 1;
        }
    }
    return ans;
}

除了求值，异或线性基还可以合并，甚至于求它和另一个异或线性基的交集与并集。所以异或线性基是一种数据结构。我把它封装在一个结构体 XorBase 里：

struct XorBase {
    ll p[64];
    bool flag;

    XorBase()
    {
        flag = false;
        memset(p, 0, sizeof p);
    }

    bool insert(ll n)
    {
        for (int i = 63; i >= 0; i--) {
            if ((n >> i) & 1) {
                if (!p[i]) {
                    p[i] = n;
                    break;
                }
                n ^= p[i];
            }
        }
        if (!n)
            flag = true;
        return n;
    }

    void rebuild()
    {
        for (int i = 63; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if ((p[i] >> j) & 1)
                    p[i] ^= p[j];
            }
        }
    }

    ll getMin()
    {
        if (flag)
            return 0;
        for (int i = 63; i >= 0; i--) {
            if (p[i])
                return p[i];
        }
    }

    ll getMax()
    {
        ll ans = 0;
        for (int i = 63; i >= 0; i--) {
            ans = max(ans, ans ^ p[i]);
        }
        return ans;
    }

    ll MaxK(ll k)
    {
        if (k == 1 && flag)
            return 0;
        if (flag)
            k--;
        rebuild();
        ll ans = 0;
        for (int i = 63; i >= 0; i--) {
            if (p[i]) {
                if (k & 1)
                    ans ^= p[i];
                k >>= 1;
            }
        }
        return ans;
    }
};

四. 并集

思路就是枚举异或线性基 A 的内容，将其中元素全部加入到 B 中。

XorBase Union(XorBase A, XorBase B)
{
    XorBase res = B;
    for (int i = 0; i <= 63; i++) {
        if (A.p[i]) {
            res.insert(A.p[i]);
        }
    }
    return res;
}

五. 交集

如果一个异或线性基里的元素插入到另一个异或线性基里会失败，则将它插入到交集异或线性基中。

XorBase Intersect(XorBase A, XorBase B)
{
    XorBase res;
    for (int i = 0; i <= 63; i++) {
        if (A.p[i]) {
            if (!B.insert(A.p[i]))
                res.insert(A.p[i]);
        }
        if (B.p[i]) {
            if (!A.insert(B.p[i]))
                res.insert(B.p[i]);
        }
    }
    return res;
}

例 4.3.1 DMG Bonus 打核爆

作为一名资深神原玩家，你希望能在新限定五星角色初进卡池时尽快拿下全网首个 999w 核爆记录，以此证明自己的实力。现在你已经在游戏里做好了很多伤害加成型的食物，准备在 boss 战时一展身手。战斗开始时，你首先给角色吃下了基础食物（每局开始前必吃的食物），它的效果是在 300 秒内单角色爆发伤害增加 70\%，但是同时它有一个副作用……

基础食物生效期内，如果角色吃下其他伤害加成型的食物，总伤害加成的百分比数值将是各种食物的伤害百分比数值的异或之和，即 D_{total}=(\bigoplus\limits_{i=2}^{n}D_{i})\times100\%，\bigoplus\limits_{i=1}^{n}D_i 表示 D_1\oplus D_2\oplus D_3\oplus\dots\oplus D_n，\oplus 为异或符号。各种食物的伤害加成在下边给出，如果不吃任何加成型食品（也不吃基础食品），爆发伤害期望值为 1400000。吃完所有食物后，如果你用增伤角色施加了 60\% 的爆发增伤。请问你的最大爆发伤害能否达到 9999999，即 10^7-1？若不能，最高伤害是多少？（令每种食物只有一份，且食物效果均可叠加，结果四舍五入到万位）

问题分析：题干信息已经很明显了，这是一道异或线性基的最大和问题。根据上文所述程序计算即可。

算法实现：这里使用的是结构体封装版本的异或线性基计算代码：

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;

struct XorBase {
    ll p[64];
    bool flag;

    XorBase()
    {
        flag = false;
        memset(p, 0, sizeof p);
    }

    bool insert(ll n)
    {
        for (int i = 63; i >= 0; i--) {
            if ((n >> i) & 1) {
                if (!p[i]) {
                    p[i] = n;
                    break;
                }
                n ^= p[i];
            }
        }
        if (!n)
            flag = true;
        return n;
    }

    void rebuild()
    {
        for (int i = 63; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if ((p[i] >> j) & 1)
                    p[i] ^= p[j];
            }
        }
    }

    ll getMin()
    {
        if (flag)
            return 0;
        for (int i = 63; i >= 0; i--) {
            if (p[i])
                return p[i];
        }
    }

    ll getMax()
    {
        ll ans = 0;
        for (int i = 63; i >= 0; i--) {
            ans = max(ans, ans ^ p[i]);
        }
        return ans;
    }

    ll MaxK(ll k)
    {
        if (k == 1 && flag)
            return 0;
        if (flag)
            k--;
        rebuild();
        ll ans = 0;
        for (int i = 63; i >= 0; i--) {
            if (p[i]) {
                if (k & 1)
                    ans ^= p[i];
                k >>= 1;
            }
        }
        return ans;
    }
} A;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        A.insert(x);
    }
    cout << (1400000 * (A.getMax() + 60 + 70) / 100) << endl;
    return 0;
}

运行代码，在输入框输入：

7
270
200
280
200
180
150
75

结果输出：8162000.000。小于所给的 10^7-1。因而不能达到目标，最高伤害 816 万。

洛谷例题：

1. P3812 [模板] 线性基
2. P4570 [BJWC2011] 元素
3. P4301 [CQOI2013] 新 Nim 游戏

后记 & 鸣谢

本文的灵感来源正是例 1.4.1，感谢这样的高智商解谜让我沉迷于线性代数无法自拔。

本文的结构安排和部分证明过程均借鉴了 \texttt{Steven J.Leon} 所著《线性代数》（原书第十版），并加以个人的理解和 OI 算法方面的拓展。如有偏颇之处烦请指出，不胜感激！

感谢 @Brailliant11001 为本文例 2.2.1 进行答案检验；@HYLW 为本文 1.3 节消元步骤进行查验；向量空间部分图片取自知乎，其余图片资源引用时请注明出处；章节例题/代码均为原创，如有错漏之处可私信我指出。