洛谷 P4783 【模板】矩阵求逆 题解
算法模板 | 线性代数 | 高斯约旦消元
题目信息
- 题目链接：https://www.luogu.com.cn/problem/P4783
- 难度：提高+/省选- 困难
- 知识点：矩阵求逆、高斯-约旦消元、模运算
一、题目简述
给定一个 (n) 阶矩阵 (A)，求它的逆矩阵 (A^{-1})，满足 (A \times A^{-1} = E)（(E) 为单位矩阵）。
若矩阵不可逆，输出 No Solution。
所有运算在模 (10^9+7) 意义下进行，输出逆矩阵的每个元素。
数据范围：
- (1 \le n \le 400)
- (0 \le A_{ij} < 10^9+7)
- 模数 (MOD = 10^9+7)（质数）
二、题目分析
核心思路
矩阵求逆的经典方法是高斯-约旦消元法（我们线性代数学过的增广矩阵与初等行变换）：
- 构造增广矩阵 ([A | E])，其中 (E) 是 (n) 阶单位矩阵
- 对增广矩阵做初等行变换，将左半部分 (A) 化为单位矩阵 (E)
- 此时右半部分即为 (A) 的逆矩阵 (A^{-1})
- 若消元过程中某列主元为0，说明矩阵不可逆
关键细节
- 模 (10^9+7) 下的除法等价于乘以乘法逆元（费马小定理求逆）
- 高斯-约旦消元无需回代，直接将主元化为1，其他列化为0，代码更简洁
- 时间复杂度 (O(n^3))，(n=400) 时可通过
三、代码实现
#include <stdio.h>#define MOD 1000000007LLlong long matrix[405][805];
int n;// 快速幂求逆元
long long power(long long a, long long b) {long long res = 1;a %= MOD;while (b) {if (b & 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;
}long long get_inv(long long n) {return power(n, MOD - 2);
}int main() {if (scanf("%d", &n) != 1) return 0;// 1. 构造增广矩阵 [A | I]for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {scanf("%lld", &matrix[i][j]);}matrix[i][i + n] = 1; // 右侧补单位阵}// 2. 高斯-约旦消元for (int i = 0; i < n; i++) {// 寻找主元，如果 matrix[i][i] 为 0，则与下方交换int pivot = i;while (pivot < n && matrix[pivot][i] == 0) pivot++;if (pivot == n) {printf("No Solution\n");return 0;}// 交换行if (pivot != i) {for (int j = 0; j < 2 * n; j++) {long long temp = matrix[i][j];matrix[i][j] = matrix[pivot][j];matrix[pivot][j] = temp;}}// 将当前行主元化为 1long long inv = get_inv(matrix[i][i]);for (int j = i; j < 2 * n; j++) {matrix[i][j] = (matrix[i][j] * inv) % MOD;}// 消除其他行的第 i 列for (int k = 0; k < n; k++) {if (k != i) {long long factor = matrix[k][i];for (int j = i; j < 2 * n; j++) {matrix[k][j] = (matrix[k][j] - factor * matrix[i][j] % MOD + MOD) % MOD;}}}}// 3. 输出右半部分 [I | A^-1]for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%lld%c", matrix[i][j + n], j == n - 1 ? '\n' : ' ');}}return 0;
}
四、复杂度分析
- 时间复杂度：(O(n^3))
高斯-约旦消元的三重循环，(n=400) 时总运算量约 (6.4 \times 10^7)，可在时间限制内通过。 - 空间复杂度：(O(n^2))
存储 (n \times 2n) 的增广矩阵，(n=400) 时占用空间约 (1.28 \times 10^6)，完全满足内存限制。
五、常见问题与避坑
- 模运算负数处理：减法后需
+ MOD % MOD，避免出现负数 - 主元选择：必须从第 (i) 行开始找，不能从第1行开始
- 逆元计算：模数 (10^9+7) 是质数，用费马小定理 (a^{MOD-2}) 求逆
- 数组大小：增广矩阵需开 (n \times 2n)，避免越界
六、总结
矩阵求逆是线性代数的核心算法，高斯-约旦消元是最常用的实现方式：
- 核心步骤：构造增广矩阵 → 主元归一 → 初等行变化消元
七、学习提高
- 本人做这一部分的时候线性代数还没学到这一部分，如同样想了解的可以观看宋浩老师的课程【初等行变换法求逆矩阵】
https://www.bilibili.com/video/BV1h7pteyEww?spm_id_from=333.788.videopod.episodes&vd_source=c435966a6ee44f8c5dd8206fec75523a&p=23 - 若想进一步学习如何用编程From Scratch的解决线性代数问题，可以去了解Data Science from Scratch（Joel Grus），这本书语言是python。代码：
https://github.com/joelgrus/data-science-from-scratch