目录​编辑前言一、矩阵基础概念认识 “数表” 的世界1.1 矩阵的定义1.2 算法中高频的特殊矩阵1.2.1 方阵1.2.2 三角矩阵1.2.3 对角矩阵1.2.4 单位矩阵二、矩阵的基本运算加减与数乘2.1 矩阵加法与减法2.2 矩阵数乘2.3 线性运算的运算规律三、矩阵乘法核心定义与运算规则3.1 矩阵乘法的前提条件3.2 矩阵乘法的结果维度3.3 矩阵乘法的核心公式3.4 实例解析手把手计算矩阵乘法3.5 矩阵乘法的重要运算规律3.5.1 不满足交换律3.5.2 满足结合律3.5.3 满足分配律3.5.4 单位矩阵的特殊性质四、洛谷真题实战 1基础矩阵乘法B21054.1 题目描述4.2 解题思路4.3 C 代码实现4.4 代码说明五、洛谷真题实战 2矩阵快速幂P33905.1 矩阵快速幂的核心思想5.2 题目描述5.3 解题思路5.4 C 代码实现5.5 代码关键说明六、矩阵乘法的进阶应用矩阵加速求解数列6.1 矩阵加速的核心思想6.2 实战矩阵加速求解斐波那契数列洛谷 P19626.2.1 构造转移矩阵6.2.2 C 代码实现总结前言线性代数是算法学习中的重要数学基础而矩阵乘法更是其中的核心内容不仅是理解后续矩阵快速幂、矩阵加速的前提还广泛应用于图论邻接矩阵、动态规划优化、数列求解等算法场景。本文将从矩阵的基本概念出发一步步拆解矩阵乘法的定义、运算规则再结合洛谷经典真题手把手实现矩阵乘法、矩阵快速幂的 C 模板同时讲解矩阵加速在数列求解中的实际应用让零基础的同学也能彻底吃透矩阵乘法下面就让我们正式开始吧一、矩阵基础概念认识 “数表” 的世界在正式学习矩阵乘法前我们首先要搞清楚什么是矩阵以及算法中常用的特殊矩阵有哪些。这些基础概念是后续所有运算的前提理解透彻才能避免后续踩坑。1.1 矩阵的定义简单来说矩阵就是由n×m 个数字排成的n 行 m 列的数表我们通常用大写字母 A、B、C 来表示矩阵其中第 i 行第 j 列的元素记作aij​。其标准形式如下比如一个 2 行 3 列的矩阵可以表示为这就是一个 2×3 矩阵。在算法中矩阵的一个典型应用就是图论的邻接矩阵—— 用一个 n×n 的矩阵存储 n 个节点的图若节点 i 和节点 j 之间有边则aij​1否则为 0通过邻接矩阵可以快速判断节点间的连通性而邻接矩阵的运算本质就是矩阵乘法。1.2 算法中高频的特殊矩阵在矩阵乘法的运算中我们会经常遇到几种特殊的方阵行数 列数的矩阵它们各自有独特的性质更是矩阵快速幂、单位矩阵运算的关键下面逐个讲解结合例子理解更直观。1.2.1 方阵行数等于列数的矩阵称为方阵比如 4×4、3×3 矩阵都是方阵。方阵中从左上角到右下角的元素构成主对角线后续的三角矩阵、对角矩阵都是基于方阵的主对角线定义的。例4 阶方阵4×41.2.2 三角矩阵三角矩阵分为上三角矩阵和下三角矩阵核心是主对角线一侧的元素全为 0上三角矩阵主对角线左下方的元素均为 0只有主对角线和右上方有非 0 元素下三角矩阵主对角线右上方的元素均为 0只有主对角线和左下方有非 0 元素。例4 阶上三角矩阵​​例4 阶下三角矩阵1.2.3 对角矩阵主对角线之外的元素均为 0的方阵称为对角矩阵简单说就是只有主对角线上有非 0 元素其余位置全 0。对角矩阵是三角矩阵的特殊形式上三角和下三角矩阵的交集就是对角矩阵。例4 阶对角矩阵1.2.4 单位矩阵主对角线的元素均为 1的对角矩阵称为单位矩阵通常用字母 E 表示。单位矩阵是矩阵乘法中的 “数字 1”任何矩阵乘以单位矩阵结果都等于原矩阵即AEEAA这一性质是矩阵快速幂的核心基础一定要牢记例4 阶单位矩阵二、矩阵的基本运算加减与数乘在学习矩阵乘法前我们先掌握矩阵的线性运算—— 加法、减法和数乘这些运算规则简单是理解复杂运算的铺垫核心要求是同型矩阵行数和列数都相同的矩阵。2.1 矩阵加法与减法矩阵加减法的规则非常直观两个同型矩阵相加减结果为对应位置的元素分别相加减。前提必须是同型矩阵比如 2×3 矩阵只能和 2×3 矩阵相加减3×3 矩阵只能和 3×3 矩阵相加减不同型矩阵无法进行加减运算结果相加减后得到的矩阵行数和列数与原矩阵保持一致。2.2 矩阵数乘矩阵数乘指的是一个数字乘以一个矩阵规则是矩阵中的每一个元素都乘以这个数字结果矩阵的行数和列数不变。这里的 “数” 可以是整数、小数正数、负数均可数乘是对矩阵的整体缩放不会改变矩阵的维度。2.3 线性运算的运算规律矩阵的加法和数乘满足交换律、结合律和分配律和我们小学学的数字运算规律基本一致记起来很容易交换律ABBA结合律(AB)CA(BC)k×(l×A)(k×l)×A分配律k×(AB)k×Ak×B(kl)×Ak×Al×A。这些规律看似简单但在后续的矩阵运算化简中会经常用到熟悉后能大幅提高运算效率。三、矩阵乘法核心定义与运算规则矩阵乘法是本文的核心重点也是和普通数字运算差异最大的部分其规则不是简单的对应元素相乘而是 “行乘列求和”且有严格的维度要求很多同学初次学习容易出错建议结合例子反复理解。3.1 矩阵乘法的前提条件矩阵 A 和矩阵 B 能够相乘的唯一前提矩阵 A 的列数 矩阵 B 的行数。如果不满足这个条件矩阵乘法无意义无法进行运算。比如A 是 n×s 矩阵n 行 s 列B 是 s×m 矩阵s 行 m 列A 的列数 sB 的行数 s满足条件可以相乘A 是 2×3 矩阵B 是 3×4 矩阵满足条件可以相乘A 是 2×3 矩阵B 是 2×3 矩阵A 的列数 3B 的行数 2不满足条件无法相乘。3.2 矩阵乘法的结果维度若 A 是 n×s 矩阵B 是 s×m 矩阵那么 A×B 的结果是一个n×m 矩阵n 行 m 列记为CAB。简单总结结果矩阵的行数等于第一个矩阵的行数列数等于第二个矩阵的列数而中间的 “s” 是两个矩阵的 “公共维度”是行乘列求和的次数。例2×3 矩阵 × 3×4 矩阵 2×4 矩阵3×5 矩阵 ×5×2 矩阵 3×2 矩阵。3.3 矩阵乘法的核心公式设 CAB其中 A 是 n×s 矩阵B 是 s×m 矩阵C 是 n×m 矩阵那么 C 中第 i 行第 j 列的元素cij​的计算公式为用通俗的语言解释就是cij​等于矩阵 A 的第 i 行所有元素与矩阵 B 的第 j 列对应位置元素分别相乘后再将所有乘积相加也就是我们常说的 “行乘列求和”。这里的 k 从 1 到 s对应 A 的第 i 行有 s 个元素B 的第 j 列有 s 个元素刚好一一对应相乘求和后得到cij​。3.4 实例解析手把手计算矩阵乘法光看公式和定义容易抽象我们用一个具体的例子手把手计算矩阵乘法把 “行乘列求和” 的规则落地看完这个例子矩阵乘法的计算就基本掌握了。步骤 1判断是否可乘 确定结果维度A 的列数 2B 的行数 2满足条件结果 C 是 3×3 矩阵n3m3。步骤 2逐行逐列计算cij​C 是 3 行 3 列需要计算 9 个元素逐个计算c11​A 第 1 行 × B 第 1 列 → 1×72×1072027c12​A 第 1 行 × B 第 2 列 → 1×82×1182230c13​A 第 1 行 × B 第 3 列 → 1×92×1292433c21​A 第 2 行 × B 第 1 列 → 3×74×10214061c22​A 第 2 行 × B 第 2 列 → 3×84×11244468c23​A 第 2 行 × B 第 3 列 → 3×94×12274875c31​A 第 3 行 × B 第 1 列 → 5×76×10356095c32​A 第 3 行 × B 第 2 列 → 5×86×114066106c33​A 第 3 行 × B 第 3 列 → 5×96×124572117步骤 3整理结果矩阵CAB3.5 矩阵乘法的重要运算规律矩阵乘法的运算规律和普通数字乘法有很大差异最核心的区别是不满足交换律这一点是算法编程中必须注意的一旦顺序写错结果完全错误下面总结矩阵乘法的核心规律3.5.1 不满足交换律一般情况下AB≠BA甚至 BA 可能无意义。原因有两点维度不允许比如 A 是 2×3 矩阵B 是 3×4 矩阵AB 是 2×4 矩阵但 BA 的话B 的列数 4A 的行数 2不满足相乘条件BA 无意义维度允许但结果不同比如 A 和 B 都是 3×3 矩阵AB 和 BA 都有意义但计算结果几乎一定不同。结论矩阵乘法中顺序决定一切AB 表示 A 左乘 BBA 表示 B 左乘 A二者完全不同编程时必须严格按照题目要求的顺序相乘。3.5.2 满足结合律A(BC)(AB)C即多个矩阵相乘时改变括号的位置运算顺序结果不变。结合律是矩阵快速幂的核心数学基础正因为有结合律我们才能像整数快速幂那样将Ak拆解为多个小矩阵的乘积实现对数级别的时间复杂度优化。3.5.3 满足分配律左分配律A(BC)ABAC右分配律(BC)ABACA。注意分配律中也要注意顺序左分配律中 A 始终在左边右分配律中 A 始终在右边不能随意交换。3.5.4 单位矩阵的特殊性质任何矩阵乘以单位矩阵结果等于原矩阵即AEEAA前提是相乘维度满足条件。比如 A 是 n×s 矩阵E 是 s×s 单位矩阵则AEAE 是 n×n 单位矩阵则EAA。单位矩阵的这一性质对应整数乘法中的 “1×xx×1x”是矩阵快速幂中初始值的设置依据。四、洛谷真题实战 1基础矩阵乘法B2105理解了矩阵乘法的定义和规则后我们结合洛谷的基础真题B2105 矩阵乘法用 C 实现基础的矩阵乘法模板。这道题是矩阵乘法的入门题核心是模拟 “行乘列求和” 的过程适合新手上手。题目链接https://www.luogu.com.cn/problem/B21054.1 题目描述计算两个矩阵的乘法n×m 阶的矩阵 A 乘以 m×k 阶的矩阵 B得到 n×k 阶的矩阵 C。输入第一行是 n, m, k随后 n 行是矩阵 A 的元素再 m 行是矩阵 B 的元素输出输出矩阵 C共 n 行每行 k 个整数元素间用空格分隔数据范围n, m, k 均小于 100矩阵元素绝对值不大于 1000。4.2 解题思路数据存储用二维数组存储三个矩阵 A、B、C由于数据范围小定义数组大小为 110 即可留余量避免越界输入处理依次输入 n, m, k再输入矩阵 A 和矩阵 B 的元素矩阵乘法核心三层循环实现“行乘列求和”外层循环遍历矩阵 A 的行共 n 行中层循环遍历矩阵 B 的列共 k 列内层循环遍历公共维度 m计算行乘列的和赋值给 C [i][j]输出结果按行输出矩阵 C 的所有元素每行 k 个空格分隔。4.3 C 代码实现#include iostream using namespace std; // 定义数组大小留余量避免越界 const int N 110; // a:矩阵A, b:矩阵B, c:结果矩阵C int a[N][N], b[N][N], c[N][N]; // n:A的行, m:A的列/B的行, s:B的列题目中的k int n, m, s; // 矩阵乘法核心函数 void mul() { for (int i 1; i n; i) { // 遍历A的行 for (int j 1; j s; j) { // 遍历B的列 for (int k 1; k m; k) { // 遍历公共维度m c[i][j] a[i][k] * b[k][j]; } } } } int main() { cin n m s; // 输入矩阵A for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } // 输入矩阵B for (int i 1; i m; i) { for (int j 1; j s; j) { cin b[i][j]; } } // 执行矩阵乘法 mul(); // 输出结果矩阵C for (int i 1; i n; i) { for (int j 1; j s; j) { cout c[i][j] ; } cout endl; } return 0; }4.4 代码说明数组下标从 1 开始符合数学中矩阵的行、列编号习惯避免下标 0 带来的混淆新手更容易理解三层循环的顺序iA 的行→ jB 的列→ k公共维度这是矩阵乘法的标准循环顺序也可以调整为 i→k→j结果一致但前者更贴合 “行乘列求和” 的直观逻辑结果矩阵初始化C 数组的初始值为 0通过累加a[i][k]∗b[k][j]得到最终的c[i][j]符合求和公式的定义。五、洛谷真题实战 2矩阵快速幂P3390掌握了基础矩阵乘法后我们来学习矩阵乘法的进阶应用 —— 矩阵快速幂这是算法竞赛中的高频考点核心是类比整数快速幂利用矩阵乘法的结合律将Ak的计算时间复杂度从O(k)优化到O(logk)适用于 k 极大的场景比如 k≤10^18。5.1 矩阵快速幂的核心思想整数快速幂的核心是 “快速幂降次”比如计算可以拆解为而不是连续乘 10 次 x。矩阵快速幂完全复用这一思想唯一的区别是整数快速幂的初始值是 1矩阵快速幂的初始值是单位矩阵 E因为单位矩阵是矩阵乘法的 “1”。简单来说矩阵快速幂的步骤为初始化结果矩阵为单位矩阵 RET将指数 k 进行二进制分解遍历每一位若当前位为 1将结果矩阵 RET 与当前的矩阵 A 相乘将矩阵 A 自乘指数右移一位除以 2直到指数 k 变为 0此时 RET 就是Ak。5.2 题目描述题目链接https://www.luogu.com.cn/problem/P3390洛谷 P3390 【模板】矩阵快速幂给定 n×n 的矩阵 A求Ak结果矩阵的每个元素对1097取模。输入第一行是 n 和 k随后 n 行是矩阵 A 的 n×n 个元素输出输出Ak的 n×n 矩阵每行 n 个元素空格分隔数据范围n≤100k≤10^18。5.3 解题思路数据结构用结构体封装矩阵方便矩阵的存储和乘法运算结构体中包含一个二维数组存储矩阵元素运算符重载重载乘法运算符*实现两个矩阵的相乘同时完成取模操作简化代码快速幂函数实现矩阵快速幂的核心逻辑初始化结果矩阵为单位矩阵按二进制分解指数 k取模操作由于 k 极大矩阵元素会溢出因此每一步乘法都要对1097取模使用 long long 类型存储矩阵元素避免整数溢出。5.4 C 代码实现#include iostream #include cstring using namespace std; typedef long long LL; const int N 110; const int MOD 1e9 7; // 取模模数 LL n, k; // n:矩阵阶数, k:指数 // 矩阵结构体 struct Matrix { LL m[N][N]; // 构造函数初始化矩阵为全0 Matrix() { memset(m, 0, sizeof(m)); } // 重载乘法运算符实现矩阵乘法 Matrix operator*(const Matrix B) const { Matrix C; // 结果矩阵 for (int i 1; i n; i) { // 遍历A的行 for (int j 1; j n; j) { // 遍历B的列 for (int t 1; t n; t) { // 遍历公共维度 C.m[i][j] (C.m[i][j] m[i][t] * B.m[t][j]) % MOD; } } } return C; } }A, ret; // A:原始矩阵, ret:结果矩阵(初始为单位矩阵) // 矩阵快速幂函数 void qpow(LL b) { // 初始化结果矩阵为单位矩阵 for (int i 1; i n; i) { ret.m[i][i] 1; } while (b) { if (b 1) { // 若当前二进制位为1结果矩阵乘当前A ret ret * A; } A A * A; // 矩阵自乘 b 1; // 指数右移一位等价于除以2 } } int main() { cin n k; // 输入原始矩阵A for (int i 1; i n; i) { for (int j 1; j n; j) { cin A.m[i][j]; } } // 执行矩阵快速幂 qpow(k); // 输出结果矩阵 for (int i 1; i n; i) { for (int j 1; j n; j) { cout ret.m[i][j] ; } cout endl; } return 0; }5.5 代码关键说明结构体与运算符重载将矩阵封装为结构体重载*运算符后矩阵相乘可以直接写为A*B和整数乘法一样直观大幅简化代码避免重复写矩阵乘法的三层循环long long 类型由于矩阵元素会不断相乘即使取模中间结果也会超过 int 的范围int 最大约 2×10^9因此必须用 long long 存储矩阵元素防止溢出单位矩阵初始化快速幂的结果矩阵初始值必须是单位矩阵这是矩阵快速幂的关键若初始化为全 0 矩阵最终结果会始终为 0完全错误二进制分解用b 1判断当前二进制位是否为 1b 1实现指数降次这是快速幂的标准操作时间复杂度为O(logk)即使 k10^18也只需循环 60 次左右效率极高。六、矩阵乘法的进阶应用矩阵加速求解数列矩阵快速幂的核心应用是矩阵加速用于求解线性递推数列的第 n 项比如斐波那契数列、递推式为ax​ax−1​ax−3​的数列等。对于递推数列当 n 极大时比如 n≤10^18动态规划的 O (n) 算法会超时而矩阵加速结合快速幂可以将时间复杂度优化到 O (logn)这是算法竞赛中的经典优化手段。6.1 矩阵加速的核心思想矩阵加速的关键是构造递推矩阵也叫转移矩阵将数列的线性递推关系转化为矩阵的幂次运算即转移矩阵其中 k 是递推式的初始项数比如斐波那契数列的递推式是Fn​Fn−1​Fn−2​初始项是 F11、F21k2。简单来说矩阵加速的步骤为根据数列的递推式构造合适的转移矩阵将数列的第 n 项转化为转移矩阵的幂次乘以初始项的矩阵用矩阵快速幂计算转移矩阵的幂次再与初始项矩阵相乘得到第 n 项。6.2 实战矩阵加速求解斐波那契数列洛谷 P1962题目链接https://www.luogu.com.cn/problem/P1962斐波那契数列是最经典的线性递推数列递推式为F1​1,F2​1,Fn​Fn−1​Fn−2​(n≥3)我们用矩阵加速结合快速幂求解。6.2.1 构造转移矩阵首先将斐波那契的递推式转化为矩阵形式验证右边矩阵相乘的结果为与左边一致。由此可以推导出通式转移矩阵就是初始项矩阵是。6.2.2 C 代码实现#include iostream #include cstring using namespace std; typedef long long LL; const int N 3; const int MOD 1e9 7; LL n; // 矩阵结构体 struct Matrix { LL m[N][N]; Matrix() { memset(m, 0, sizeof(m)); } // 重载乘法运算符 Matrix operator*(const Matrix B) const { Matrix C; for (int i 1; i 2; i) { for (int j 1; j 2; j) { for (int t 1; t 2; t) { C.m[i][j] (C.m[i][j] m[i][t] * B.m[t][j]) % MOD; } } } return C; } }A, ret; // 矩阵快速幂 void qpow(LL b) { // 初始化结果矩阵的初始值对应初始项[F2,F1] ret.m[1][1] 1; ret.m[1][2] 1; // 构造转移矩阵 A.m[1][1] 1; A.m[1][2] 1; A.m[2][1] 1; A.m[2][2] 0; while (b) { if (b 1) { ret ret * A; } A A * A; b 1; } } int main() { cin n; // 初始项直接输出 if (n 1 || n 2) { cout 1 endl; return 0; } // 计算转移矩阵的n-2次幂 qpow(n - 2); // 结果为ret.m[1][1] cout ret.m[1][1] endl; return 0; }总结矩阵乘法看似抽象但只要掌握了核心规则和模板再结合真题反复练习就能彻底吃透。作为算法学习的重要基础矩阵乘法的掌握程度直接影响后续复杂算法的学习希望本文能帮助大家从入门到实战彻底搞懂矩阵乘法