算法竞赛中的线性代数

线性代数

一、高斯-约旦消元 1. 求解线性方程组

约旦消元法的精度更好、代码更简单，没有回带的过程

1. 选择一个尚未被选过的未知数作为主元，选择一个包含这个主元的方程

2. 将这个方程主元的系数化为1

3. 通过加减消元，消掉其它所有方程中的这个未知数

4. 重复以上步骤，直到把每一行都变成只有一项有系数

给出一道例题：P3389 【模板】高斯消元法 - 洛谷

算法说明：

高斯约旦消元是一列一列来处理的，

对于第 i i i 列，其前 i − 1 i-1 i−1 列除了对角线上的元为 1 1 1 ，剩下的元均为 0 0 0 ，

让这一列的数同乘一个系数，使得 m a t [ i ] [ i ] mat[i][i] mat[i][i] 为 1 1 1 ，

然后对 1 ∼ n 1\sim n 1∼n 行用第 i i i 行来减，最后这一列除了 m a t [ i ] [ i ] mat[i][i] mat[i][i] 为 1 1 1 ，剩下值均为 0 0 0

循环下去，最终的解存储在 m a t [ i ] [ n + 1 ] mat[i][n+1] mat[i][n+1] 中

2. 计算行列式

计算行列式则相对要简单一些，化成上上三角阵后，对对角线进行求积即可

给出一道例题： P7112 【模板】行列式求值 - 洛谷

算法说明：

本题是一个整数矩阵，在消元过程中有些不一样的，

题目不能保证逆元的存在性，因此采用了辗转相除法来解决本题

算法也是一列一列的来处理，处理到第 i i i 列时，前 i − 1 i-1 i−1 列已变成上三角阵了

利用辗转相除法，对第 i ∼ n i \sim n i∼n 行进行辗转相除，使得 i + 1 ∼ n i+1\sim n i+1∼n 行的 m a t [ σ ] [ i ] mat[\sigma][i] mat[σ][i] 均为 0 0 0 ，即第 i i i 列也变成了上三角阵，然后再 a n s ∗ = m a t [ i ] [ i ] ans*=mat[i][i] ans∗=mat[i][i] 即可

3. 矩阵求逆

矩阵求逆和求解线性方程挺像，也采用高斯约旦消元，一列一列的消，最后左边是单位阵，右边是逆矩阵，即 [ A , I ] ⇒ [ I , A − 1 ] [A,I] \rArr [I,A^{-1}] [A,I]⇒[I,A−1]

给出一道例题： P4783 【模板】矩阵求逆 - 洛谷

算法说明：

其实思路和“求解线性方程组”的思路几乎一样，不过这里的逆元不再是直接除了，而是利用快速幂来获得逆元

4. 算法比较 求解线性方程组计算行列式矩阵求逆需要消出 I I I是否是是高斯约旦是否是答案存储至矩阵数矩阵 i n t int int 型逆元快速幂辗转相除快速幂 f l o a t float float 型逆元分数分数分数 求解线性方程组（ int 型）

#include 
#define int long long
using namespace std;
const int maxn = 111;
const int mod = 1e9 + 7;
int mat[maxn][maxn];
int quickpow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return ans;
}
bool gauss(int n) {
  for (int i = 1; i = i; j--)  // 循环顺序不可改
      mat[i][j] = mat[i][j] * quickpow(mat[i][i], mod - 2) % mod;
    for (int j = 1; j