核心概述
模逆矩阵：在模素数 p 的有限域内对非奇异方阵 A 求 A^{−1}（mod p），通常用高斯–约当消元并以模逆替代除法，时间复杂度 O(n^3)。
原文引述
Description: Compute A^{-1} modulo a prime p via Gauss–Jordan elimination with modular inverses (or adjugate). Requires det(A) mod p ≠ 0. Time: O(n^3) Status: tested ——摘自本节点现有英文注释
展开阐述
-
函数/接口（据实现）
- vector<vector
> invMod(const vector<vector >& A, ll mod) - 返回 A 在模 mod 下的逆（mod 为素数或保证可逆的域）；若不可逆则返回空或报错。
- bool invertibleMod(const Mat& A, ll mod)：可选的可逆性检查。
- 依赖：
- 088-数论-模逆：用于主元的模逆。
- 091-数论-模幂：可选（用 powmod 代替 exgcd）。
- 094-数论-模运算：规范化的加减乘。
- vector<vector
-
核心算法（Gauss–Jordan with Mod）
- 构造增广矩阵 [A | I]（n×2n），所有元素先规约到 [0,mod)。
- 对 i=0..n−1：
- 寻找第 i 列从行 i 起的第一个非零元所在行 p；若不存在则 A 奇异（det≡0 mod p）。
- 若 p≠i，交换第 i 与 p 行。
- 计算主元的逆 invPiv = inv(A[i][i], mod)（见 088-数论-模逆）。
- 将主元行乘 invPiv 使其变为 1：A[i][j] = A[i][j]*invPiv % mod。
- 对所有行 j≠i，消去第 j 行第 i 列：factor = A[j][i]；row_j ← row_j − factor·row_i（每步取模）。
- 右侧部分即为 A^{−1} mod p。
-
数值与实现注意
- 所有运算在模域内进行，需保持 0≤x<mod；加减乘后取模，除法用乘逆元代替。
- 素数模保证了除数与模互质（非零元素皆可逆）；若模非素数，需判断 gcd(piv,mod)==1，否则矩阵在模域不可逆。
- 主元选择：可选部分主元（按列绝对值或随机）以改善数值/模域性能，但并非必须。
- 空间优化：可直接在 A 上进行原地操作，覆盖原矩阵为逆矩阵。
-
输出语义
- 返回 n×n 矩阵 B，满足 (A·B) mod p = I；若不可逆，返回空或抛出。
-
复杂度
- O(n^3) 次模乘加与模逆；单次模逆 O(log mod)（若用扩展欧几里得）或 O(log mod) 次模乘（若用费马小定理）。
-
使用与注意
- 依赖：mod 为素数时，可直接用 powmod(a, mod−2) 取逆；否则需 exgcd 并检查 gcd。
- 可逆性检查：若只需求解 Ax=b 而不需要 A^{−1}，可用高斯消元（114-数值算法-线性方程求解）更高效。
- 与整数逆矩阵的关系：若要求精确整数逆矩阵，可用 107-数值算法-矩阵求逆（实数）或 Bareiss+伴随矩阵，或在多个素模下求逆后用 081-数论-中国剩余定理 合并（CRT 重建）。
- 优化：
- 预计算逆元或使用快速幂加速多个矩阵求逆。
- 对稀疏或特殊结构矩阵（三角、块对角）可优化。