先问一个问题给你一个 n×n 的矩阵要你求它的行列式对任意模数 p 取模后的结果你会怎么做很多人的第一反应是这有什么难的对角线相乘再相减呗。二阶三阶确实能口算但一旦 n 到了 500暴力展开就直接炸了——行列式的定义展开是 n! 项n20 都跑不动。这也是为什么“行列式求值”会被拿出来单独当模板题它背后的高斯消元思想几乎是所有线性代数类算法题的入场券。P7112 这道模板题的刁钻之处在于模数 p 并不保证是质数。这意味着你不能像初学时那样默认每个非零元素都能求逆元。我当年第一次交的时候用的就是质数模数下最顺手的“求逆元消元”写法结果华丽丽地 WA 成一片。后来才明白这题真正考察的是你在“没有逆元”的情况下怎么完成消元。这篇文章我会把这道模板题从原理到代码完整拆一遍行列式为什么能靠初等变换求、模数非质数时到底卡在哪、最终那份能直接抄进模板库的 C 代码长什么样。末尾再聊聊我在写这题前后踩过的一些坑。1. 行列式求值到底在求什么从定义到可计算的路径1.1 行列式的定义展开为什么不可行行列式的严格定义是拉普拉斯展开对于一个 n 阶方阵 Adet(A) Σ_{j1}^{n} (-1)^{ij} a_{ij} M_{ij}其中 M_{ij} 是去掉第 i 行第 j 列后的余子式。这个定义很优雅但它天然带着 n! 的复杂度。n10 就是三百多万项n20 是 2.43e18 项别说算了光枚举就足以让机器冒烟。所以在算法题里“暴力按定义展开”从来都不是选项。那怎么办答案是回到行列式的三个基本性质上去。1.2 三条初等变换的“铁律”行列式有三个和初等行变换直接挂钩的性质它们就是所有行列式算法的地基交换两行行列式变号乘 -1。某一行整体乘以常数 k行列式乘以 k。某一行加上另一行的 k 倍行列式不变。这三条性质看起来简单但加起来的威力很大。第三条尤其关键它允许我们通过“把某一行的若干倍加到另一行上”在不改变 det 值的前提下把矩阵削成上三角形式。第二条则提醒我们如果为了消元方便把某行统一乘了个系数最后算乘积时得把系数除回去。实战中我们一般不干这种事所以这条常常只在理论证明里出现。1.3 高斯消元把行列式变成对角线的乘积有了这三条铁律求行列式的思路就顺理成章了用初等行变换把矩阵化为上三角矩阵左下角全为 0那么行列式就等于主对角线元素的乘积再乘上 (-1)^(交换行次数)。为什么上三角矩阵的行列式等于对角线乘积因为此时按第一列展开只有左上角元素对应的余子式非零一路递归下去剩下的就是所有对角线元素的乘积。于是算法骨架就出来了枚举每一列 i用第 i 行去消下面所有行的第 i 列把 a[j][i]ji全部变成 0。消元操作用的是“行 i 的某个倍数加到行 j”不改变行列式。若发现 a[i][i] 为 0就和下面某一行的第 i 列非零的行交换同时记住符号翻转一次。最后把对角线乘起来就是答案。这个过程复杂度是标准的高斯消元 O(n^3)和 n! 完全不在一个量级。这也是“行列式求值”能成为模板题的根本原因——它把线性代数里的核心消元思想和编码细节浓缩在了一起。2. 模数不互质时的难题为什么逆元方案会翻车2.1 模质数下的“舒适区”写法如果模数 p 是质数高斯消元求行列式可以写得很舒服。因为 1 到 p-1 的每个数在模 p 下都有逆元所以算 t a[j][i] * inv(a[i][i]) mod p 完全可行直接把第 i 行放大 inv(a[i][i]) 倍再把第 j 行减去它。为了不改变行列式值也可以不做归一化而是直接用 a[j][i] / a[i][i] 这种“隐形除法”。以下是典型的质数模数版本费马小定理求逆元long long qpow(long long a, long long b, long long mod) { long long res 1; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; } long long detModPrime(vectorvectorlong long a, long long mod) { int n a.size(); long long ans 1; for (int i 0; i n; i) { if (a[i][i] 0) { for (int j i 1; j n; j) { if (a[j][i] ! 0) { swap(a[i], a[j]); ans -ans; break; } } } if (a[i][i] 0) return 0; long long inv qpow(a[i][i], mod - 2, mod); for (int j i 1; j n; j) { long long t a[j][i] * inv % mod; if (t 0) continue; for (int k i; k n; k) { a[j][k] (a[j][k] - t * a[i][k] % mod mod) % mod; } } ans ans * a[i][i] % mod; } return (ans % mod mod) % mod; }这个写法在 p 为质数时又快又稳很多学校的教材和博客都这么教。2.2 任意模数下的“灵异事件”问题来了模板题的 p 不一定是质数。一旦 p 是合数上述代码里的 inv 就可能不存在。举个最简单的例子mod 6主元 a[i][i] 2gcd(2, 6) 2 ≠ 1模 6 下没有哪个数乘以 2 能等于 1逆元直接求不出来。哪怕你强行用扩展欧几里得算出来的也是一句“无解”。这还不是最坑的。还有更隐蔽的情况主元 a[i][i] 本身不是 0但它和模数不互质导致求逆失败或者求出来的“逆元”是假的乘进去之后答案完全不对。这种错靠肉眼调试很难发现因为它在小样例上可能刚好碰上互质的数能跑对一旦数据变大就可能 WA。所以面对“任意模数求行列式”这种需求必须放弃“除以主元”的思路改用另一个工具辗转相除法。2.3 辗转相除法消元的动机辗转相除法欧几里得算法求 gcd 只依赖减法和取模不需要逆元。把它应用到矩阵消元上思路是与其一次性把 a[j][i] 消成 0不如一步一步模仿欧几里得算法把“两个数”逐步减小直到其中一个变成 0。具体来说对于第 i 列当前行 i 的值为 x a[i][i]要清理的行 j 的值为 y a[j][i]。我们做若 y 0这行已经清理完了跳过。否则我们盯着 x 和 y 这一对数当 x ≥ y 时把第 j 行的若干倍从第 i 行里减掉使得 x 变成 x mod y然后交换两行让较小的 y 回到对角线位置。这本质上就是“较大的数减去较小的数的若干倍”和欧几里得算法一模一样。重复这个过程直到 y 变成 0。此时第 j 行第 i 列已经清理完而第 i 行第 i 列存的是原来这一列所有非零元素与 x 的 gcd。整个过程只用到了行倍加和行交换完全不需要逆元。这就是为什么这道模板题要用辗转相除消元不是因为它更“高级”而是因为它对模数没有要求在模数是合数时依然正确代码量也只比逆元版多一点点。3. 模板代码的核心套路辗转相除消元全过程3.1 可以抄进模板库的完整代码#include bits/stdc.h using namespace std; typedef long long ll; ll det(vectorvectorll a, ll mod) { int n (int)a.size(); ll ans 1; for (int i 0; i n; i) { for (int j i 1; j n; j) { while (a[j][i]) { ll t a[i][i] / a[j][i]; for (int k i; k n; k) { a[i][k] (a[i][k] - t * a[j][k] % mod mod) % mod; } swap(a[i], a[j]); ans -ans; } } ans ans * a[i][i] % mod; } return (ans % mod mod) % mod; }就这么短。十几行代码能兼容任意正整数模数。下面逐段说明它做了什么。3.2 为什么这样写一行行拆开看先说外层for (int i 0; i n; i) 枚举对角线位置。内层for (int j i 1; j n; j) 枚举要清理的每一行。核心是那个 while (a[j][i])。while 的条件是“第 j 行第 i 列还不为 0”只要不为 0 就说明还有没消掉的东西。循环体做三件事计算 t a[i][i] / a[j][i]。注意这里用的是 C 整数除法因为我们存的一直是非负整数都在 [0, mod) 范围内所以这是标准的“被除数 / 除数”得到的是向下取整的商。这个 t 表示“当前对角线元素是下面那个元素的多少倍”。t 可能为 0此时 a[i][i] a[j][i]说明该轮到“下面”的数去消“上面”的数了接下来交换行就能交换两者的地位。把第 i 行的 t 倍从第 i 行自己里减掉a[i][k] (a[i][k] - t * a[j][k]) % mod。这是“第 i 行加上第 j 行的 (-t) 倍”属于不改变行列式的初等变换。做完之后原本的 a[i][i] 变成了 a[i][i] mod a[j][i]相当于取了余数。交换第 i 行和第 j 行ans -ans。这相当于把“余数”换到对角线位置把原来的除数换到下面继续处理同时记录一次符号翻转。整个循环就是欧几里得算法的矩阵版两个要消的数不断互相取余、交换位置直到其中一个是 0。循环退出时第 j 行第 i 列必然是 0而且我们通过一系列合法初等变换没有改变行列式的绝对值只可能改变符号已经实时记录在 ans 里了。最后一行 ans ans * a[i][i] % mod 是把当前对角线元素乘进答案。此时由于第 i 列下方全部是 0矩阵已经逐步变成上三角行列式就等于对角线乘积。3.3 边界情况零主元、零行、模数为 1有个问题很容易被忽略如果 a[i][i] 一开始就是 0内层那个 t a[i][i] / a[j][i] 不就变成 0 了吗会不会死循环不会。因为 while 的判断条件是 a[j][i] ! 0。若 a[i][i] 0 且 a[j][i] ! 0则 t 0第一行减完还是原样交换后 a[i][i] 变成原来的 a[j][i]非零a[j][i] 变成原来的 a[i][i] 0循环退出。也就是说这个 while 天然就完成了“把非零主元交换到对角线”的工作不需要额外写 if (a[i][i] 0) 找交换行。这是一个很漂亮的写法但也容易让初次看代码的人懵原来 a[i][i]0 时 t0 的那一轮交换本身就是找主元。如果对角线和下方全为 0即 a[i][i] 和所有 a[j][i] 都是 0那么 while 不会进入最后 ans 乘 0得 0。这是正确的有一列全为 0 的行列式就是 0。模数为 1 时所有元素都是 0答案是 0代码也能正确返回 0。我见过有人在模数可能为 1 的题目里忘了特判结果在取模运算里出现除以 0 的假象其实这里的代码没问题因为用的都是整数除法除数是 a[j][i] 而非 mod。4. 复杂度、数据范围与优化方向4.1 这个模板的实际复杂度先给结论最坏情况下是 O(n^3 log mod)空间 O(n^2)。其中 n 是矩阵阶数mod 是模数大小。通俗解释一下外层 i 循环 n 次内层 j 循环 O(n) 次每一个方格上的数在 while 里被不断“取余缩小”次数受欧几里得算法步数限制约为 O(log mod)。每一次 while 内部还有一层从 i 到 n 的 for 循环长度平均 n/2。把这三层乘起来总体是 O(n^3 log mod) 级别。但实际运行中欧几里得算法的步数很少到达 log mod 的上限平均常数很小尤其当模数是 1e9 附近时每对数通常几步就到 0。所以 n500 时代码在 C 下跑起来也就零点几秒到一两秒完全能接受。n1000 则建议谨慎可能要卡常。4.2 常数优化类型、传参、取模如果你要拿这份模板去冲更极限的数据有几个优化点值得做用 int 代替 long long 存矩阵。当 mod ≤ 1e9 时两个 int 相乘最大约 1e18会溢出 int所以不能简单全用 int。稳妥做法是数组用 int 存运算时临时转 long long乘完取模完再存回 int。这样既省内存n^2 个 int 比 long long 省一半又减少缓存压力。矩阵别用值传递。上面的代码为了清晰参数写的是 vectorvector a这是拷贝整个矩阵O(n^2) 的复制代价。在极限数据下这个复制可能比消元本身还慢。建议改成传引用ll det(vectorvector a, ll mod)然后在函数内部做一份拷贝如果需要保留原矩阵或者直接原地修改。比赛里我一般直接原地修改。提前取模。t * a[j][k] 可能接近 1e18虽然 long long 下通常够用但写严谨点可以先 t % mod 再乘能进一步降低溢出风险。4.3 从模板题到实战矩阵树定理与行列式的用途可能有读者问我学这种模板除了刷题还能干嘛最常见的直接应用是矩阵树定理Matrix-Tree Theorem一个无向图的生成树个数等于它的拉普拉斯矩阵去掉任意一行一列后的行列式。很多计数题都会把它和任意模数组合在一起比如“模 1e97 求生成树个数”这类题用上面的模板直接就能写。另一个场景是解带模线性方程组时判断系数矩阵是否可逆行列式对模数取模不为 0通常意味着矩阵可逆。还有某些容斥计数、组合数学公式里需要多次计算小矩阵的行列式模板同样通用。只要遇到“任意模数 行列式”第一反应就应该是这篇文章里的写法而不是逆元版本。5. 我整理这个模板时踩过的几个坑5.1 逆元写法的“偶然正确”我第一次写这题时觉得“模板题嘛mod 多半是质数”直接交了质数版本的代码。小数据全对但交上去连 WA 几发。后来才发现题目模数真的可以是合数。这个问题最阴的地方在于如果数据构造得不够强逆元版本在某些小样例上也能碰巧跑对让你根本察觉不到写法选错了。所以后来我养成了一个习惯凡是题目没明说“模数为质数”行列式一律用辗转相除版不赌运气。5.2 交换行之后符号忘了翻转这个坑其实很小但它能让你 Debug 到怀疑人生。尤其是欧几里得循环里交换很可能发生多次如果你只在“发现 a[i][i]0 时”交换了一次、翻转了一次符号后面 while 里每次 swap 也都是一次行列式变号漏掉任何一次都会导致答案错。我建议把 ans -ans 写在 swap 后面不要试图“统计交换次数最后再处理”那样更容易数错。5.3 负数取模的统一处理行列式的中间结果在辗转相除中是会变负的。比如 a[i][k] - t * a[j][k] 可能变成负数而 C 的 % 运算在负数上会留下负号如果不处理后面所有判断和整数除法都会出错。所以每次取模后都要再加一个 mod 再取模((x % mod) mod) % mod。这行代码看起来啰嗦但它是整个模板的稳定性保障。我还见过有人用 if (x 0) x mod 代替两种都行个人更推荐统一写法不容易漏。5.4 vector 传值导致的 TLE这是另一个隐蔽的性能杀手。模板看着不复杂但如果参数是 vectorvector a每次调用 det 都会把整个矩阵复制一遍n500 时一次就是 25 万个 long long 的拷贝两次调用就多出一倍的浪费。如果题目有多组数据时间直接翻倍。改动方法很简单定义成 vectorvector a然后明确函数会修改原矩阵如果想保留原矩阵可以在函数体里手动拷贝一份。这个取舍自己在工程里定但千万别因为传参问题白白丢分。