因为这几天在写线性代数的课后习题，看到有基础线性代数的题单，所以尝试写题目将线代的用编程表示，但感到有点小难^0^。只写了一点题目。
行列式求值
（数学线性代数）
线性代数的求值（除低阶）一般是将其进行一系列的变换 按行（列）展开，换成代数余子式乘积之和（将一行（列）转换成只有一个非零元素，然后换成代数余子数）
低阶矩阵的直接公式 (n ≤ 3)
二阶 (2x2):
如果矩阵A = [a b; c d]，则det(A) = ad - bc。三阶 (3x3): 常用沙路法则 (Sarrus' Rule)：
如果矩阵A = [a b c; d e f; g h i]，则：
det(A) = aei + bfg + cdh - ceg - bdi - afh方法：将前两列复制到矩阵右侧，形成3x5的矩阵。计算三条“主对角线”(从左上到右下)上元素乘积之和，减去三条“副对角线”(从左下到右上)上元素乘积之和。
按行或列展开 (余子式展开 / 拉普拉斯展开)
适用于任意阶方阵，尤其当某行或某列有较多零时比较高效。
概念：
余子式 (Minor)
Mᵢⱼ: 删除矩阵的第i行和第j列后，得到的(n-1)x(n-1)子矩阵的行列式。代数余子式 (Cofactor)
Cᵢⱼ:Cᵢⱼ = (-1)ⁱ⁺ʲ * Mᵢⱼ。符号(-1)ⁱ⁺ʲ形成一个棋盘格图案（左上角为+）。
展开方法： 选择任意一行
i或任意一列j进行展开。按第
i行展开：det(A) = aᵢ₁Cᵢ₁ + aᵢ₂Cᵢ₂ + ... + aᵢₙCᵢₙ = Σⱼ₌₁ⁿ (aᵢⱼ * Cᵢⱼ)按第
j列展开：det(A) = a₁ⱼC₁ⱼ + a₂ⱼC₂ⱼ + ... + aₙⱼCₙⱼ = Σᵢ₌₁ⁿ (aᵢⱼ * Cᵢⱼ)
策略： 通常选择零元素最多的那一行或列进行展开，以减少计算量。
行化简法 (高斯消元法)
这是计算行列式最常用、最系统化的方法，尤其适合高阶矩阵和计算机实现。
核心思想： 利用初等行变换将矩阵化为上三角矩阵(或下三角矩阵)。上三角矩阵的行列式等于其主对角线元素的乘积。
步骤：
对矩阵进行初等行变换（三种基本操作）：
(Rᵢ ↔ Rⱼ): 交换两行。
(kRᵢ → Rᵢ): 用非零常数
k乘以某一行。(Rᵢ + kRⱼ → Rᵢ): 将一行的
k倍加到另一行上。
记录变换过程中行列式值的变化：
交换两行 (Rᵢ ↔ Rⱼ)： 行列式值变号。
det(new) = -det(old)。用非零常数
k乘某一行 (kRᵢ → Rᵢ)： 行列式值乘以k。det(new) = k * det(old)。将一行的倍数加到另一行 (Rᵢ + kRⱼ → Rᵢ)： 不改变行列式值。
det(new) = det(old)。
将矩阵化简为上三角矩阵
U。计算上三角矩阵
U的行列式：det(U) = u₁₁ * u₂₂ * ... * uₙₙ（主对角线元素乘积）。根据步骤2中记录的行变换对
det(U)进行修正，得到原始矩阵的行列式det(A)。设进行了
s次行交换操作。设用于行乘法的常数分别为
k₁, k₂, ..., kₘ(即你对第i₁行乘了k₁，对第i₂行乘了k₂，等等)。则
det(A) = (-1)ˢ * det(U) / (k₁ * k₂ * ... * kₘ)重要提示： 在化简过程中，如果进行了行乘法操作，最终必须除以这些常数因子。一个常见的技巧是避免使用行乘法操作 (kRᵢ → Rᵢ)，或者只在必要时使用（例如为了得到主元1），并仔细记录这些操作。如果完全不使用行乘法，则公式简化为
det(A) = (-1)ˢ * det(U)。
优点： 计算高效、系统化，易于编程。
利用行列式的性质
行列式有许多重要性质，有时可以直接用来计算或简化计算：
三角矩阵的行列式： 上三角或下三角矩阵的行列式等于主对角线元素之积。
分块三角矩阵的行列式： 如果方阵能分块为
A = [P Q; 0 R]或A = [P 0; S R]，其中P和R也是方阵，则det(A) = det(P) * det(R)。行列式与转置：
det(Aᵀ) = det(A)。行列式与矩阵乘法：
det(AB) = det(A) * det(B)。行列式与逆矩阵： 如果
A可逆，则det(A⁻¹) = 1 / det(A)。行列式与特征值：
det(A)等于其所有特征值λᵢ的乘积：det(A) = λ₁ * λ₂ * ... * λₙ。但这通常不是计算行列式的首选方法。奇异性：
det(A) = 0当且仅当A是奇异矩阵（不可逆）。
这些性质可以单独使用或与其他方法（特别是行化简法）结合使用来简化计算。
递归法 (本质上是按展开定义的实现)
利用行列式按行/列展开的定义，递归地计算越来越小的子矩阵的行列式，直到降到2阶或3阶可以用直接公式计算为止。
虽然概念清晰，但对于高阶矩阵计算量会非常大（时间复杂度为
O(n!)），不如行化简法高效 (O(n³)），通常不用于手算高阶矩阵。
（编程解决方法）
我想到的方法是将其转换成三角行列式来写，这样他的值就是对角线上的值乘积。方法的话我是看了题解使用了我最容易理解的辗转相消法。
但还要其他方法：
1. 高斯消元法（Gaussian Elimination）
(1) 标准高斯消元（模质数）
适用条件：MOD 是质数
原理：
通过初等行变换将矩阵化为上三角矩阵。
每次选取非零主元，用模逆元 aji⋅aii−1mod MOD 消元。
代码片段：
int det = 1; for (int i = 0; i < n; i++) { int pivot = i; while (pivot < n && !a[pivot][i]) pivot++; if (pivot == n) return 0; if (pivot != i) swap(a[i], a[pivot]), det = -det; det = 1LL * det * a[i][i] % MOD; int inv = mod_inv(a[i][i], MOD); // 求模逆元 for (int j = i + 1; j < n; j++) { int factor = 1LL * a[j][i] * inv % MOD; for (int k = i; k < n; k++) a[j][k] = (a[j][k] - 1LL * factor * a[i][k] % MOD + MOD) % MOD; } } return (det + MOD) % MOD;
(2) 辗转相消法（模任意数）
适用条件：MOD 是任意整数（给定代码的方法）
原理：
用欧几里得算法替代除法，通过行间辗转相减消元。
避免求逆元，适用于非质数模数。
优点：通用性强，不依赖 MOD 的质数性质。
2. 分治策略
(1) Schur 补（Schur Complement）
原理：
将矩阵分块 M=[ABCD]。
行列式满足 det(M)=det(A)⋅det(D−CA−1B)。
要求：
子矩阵 AA 可逆（需检查 det(A)≠0mod MOD）。
复杂度：O(n3)，但常数较大。
3. 组合数学方法
(1) Laplace 展开（递归法）
原理：
递归定义：det(A)=∑j=1n(−1)i+jaijdet(Mij)。
其中 Mij 是删除第 i行第 j 列的余子式。
缺点：
时间复杂度 O(n!)，仅适用于极小矩阵（n≤10）。
(2) 莱布尼茨公式
原理：
直接计算：det(A)=∑σ∈Snsgn(σ)∏i=1nai,σ(i)。
缺点：
需要枚举所有 n! 个排列，效率极低。
4. 黑盒算法
(1) 随机化算法（Schwartz-Zippel 引理）
原理：
给变量赋随机值，计算多项式矩阵的行列式。
通过概率验证结果（错误率可控）。
优点：
适用于稀疏矩阵，复杂度可低于 O(n3)。
缺点：
结果有概率性，需多次验证。
(2) Hessenberg 矩阵转化
原理：
将矩阵转化为上 Hessenberg 矩阵（次对角线以下为0）。
用递推关系计算行列式。
复杂度：O(n3)，但常数优于高斯消元。
5. 模数分解（中国剩余定理，CRT）
适用条件：MOD 是合数
步骤：
分解 MOD=m1×m2×⋯×mk（各 mi 互质）。
对每个 mimi 计算行列式 di=det(A)mod mi（可用高斯消元）。
用中国剩余定理合并结果：det(A)≡dimod mi。
优点：将问题转化为质数模数下的子问题。
缺点：需分解模数，增加额外计算。
总结：方法选择建议
| 场景 | 推荐方法 |
|---|---|
| MODMOD 是质数 | 标准高斯消元（模逆元） |
| MODMOD 是任意整数 | 辗转相消法 |
| 矩阵很小（n≤10n≤10） | Laplace 展开 |
| MODMOD 是合数且易分解 | CRT + 高斯消元 |
| 需要理论保证或稀疏矩阵 | 随机化算法 |
例题：
P7112 【模板】行列式求值
思路： 这题我就是用辗转相消法将其转换成三角行列式来写的。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
long long mod, n;
long long a[602][602];
int Sol() {
int w = 1;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
while (a[i][i]) {
long long mip = a[j][i] / a[i][i];
for (int z = i; z < n; z++) {
a[j][z] = (a[j][z] - a[i][z] * mip % mod+mod) % mod;
}
swap(a[i], a[j]);
w = -w;
}
swap(a[i], a[j]);
w = -w;
}
}
return w;
}
int main(){
ios::sync_with_stdio(false); // 禁用同步
cin.tie(nullptr); // 解除cin与cout绑定
cin >> n >> mod;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
int w=Sol();
long long sum = 1;
for (int i = 0; i < n; i++) {
sum = (sum * a[i][i]+mod) % mod;
}
cout << (w * sum+mod)%mod << endl;
return 0;
}