基础线性代数
因为这几天在写线性代数的课后习题，看到有基础线性代数的题单，所以尝试写题目将线代的用编程表示，但感到有点小难^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;
}