首页

# 高斯 - 约旦消元

传送门

给出 n 个方程组成的线性方程组求解。

把矩阵通过每列化成对角阵，流程如下。

  1. 枚举每一列，从剩余行中找出该列中数字最大的一行，并把找到的行换到当前行（与列下标相同），也就是说找到的这个数字现在应该在(i,i)(i, i)
  2. 通过初等行变换，把该列其他数字全部变成 0。
  3. 重复至化成对角阵。

code:

#include <cstdio>
#include <iostream>
#include <cmath>
#define rep(i, s, t) for(int i = s; i <= t; i++)
using namespace std;
const double eps=1e-7;
const int MAXN = 105;
int n;
double a[MAXN][MAXN];
int main()
{
#ifdef _WIN32
	freopen("in.txt", "r", stdin);
#endif
	scanf("%d", &n);
	rep (i, 1, n)
		rep (j, 1, n + 1)
			scanf("%lf", &a[i][j]);
	rep (i, 1, n) // 枚举每一列（即接下来要保留 a [i][i]，该列其他数字通过初等行变换变成 0）
	{
		int now = i;
		rep (j, i + 1, n) // 找出剩余行里，该列数字最大的行
			if (fabs(a[j][i]) > fabs(a[now][i]))
				now = j;
		if (fabs(a[now][i]) < eps) // 全是 0，不是满秩，无唯一解
		{
			printf("No Solution\n");
			return 0;
		}
		swap(a[i], a[now]); // 找出的行放到当前要保留的行
		rep (j, 1, n)
		{
			if (i == j) continue;
			double d = a[j][i] / a[i][i]; // 要该列其他行的数字都变成 0
			rep (k, i, n + 1) // 初等行变换，非齐次还有一列
				a[j][k] -= a[i][k] * d;
		}
	}
	rep (i, 1, n) // 最终得到对角阵，统计答案
		printf("%.2lf\n", a[i][n + 1] / a[i][i]);
	return 0;
}

# 求逆矩阵（取模）

传送门

给出 N×NN \times N 大小的矩阵，求逆矩阵，结果对 1e9+71e9 + 7 取模。

用这个东西： [A∣E]→[E∣A−1][A\space|\space E] \rightarrow [E\space|\space A^{-1}]​

用高斯 - 约旦消元直接做，记得求逆元。

code:

#include <cstdio>
#include <iostream>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
using ll = long long;
const int MAXN = 405;
const ll MOD = 1e9 + 7;
int n;
ll a[MAXN][MAXN], b[MAXN][MAXN]; //a 原矩阵，b 跟 a 并在一起的单位矩阵，写成 a [n][n<<1] 可能方便些 (?)
inline ll inv(ll num) {
  ll ans = 1, bb = MOD - 2;
  num = (num % MOD + MOD) % MOD;
  for (; bb; bb >>= 1ll) {
    if (bb & 1ll) ans = (num * ans) % MOD;
    num = (num * num) % MOD;
  }
  return ans;
}
int main()
{
  //freopen("in.txt", "r", stdin);
  scanf("%d", &n);
  rep (i, 1, n)
    rep (j, 1, n)
      scanf("%lld", &a[i][j]);
  rep (i, 1, n)
    b[i][i] = 1;
  rep (i, 1, n) // 枚举每一列
  {
    int now = i;
    rep (j, i + 1, n) // 找出这列最大数字所在行
      now = a[j][i] > a[now][i] ? j : now;
    if (!a[now][i]) // 不是满秩，不可逆
    {
      printf("No Solution\n");
      return 0;
    }
    if (now != i) // 找出的行交换至当前行
    {
      swap(a[i], a[now]);
      swap(b[i], b[now]);
    }
    ll div = inv(a[i][i]); // 行变换，第 j 行第 k 列要减去 matrix [i][k] * (a [j][i] /a [i][i])
    rep (j, 1, n) // 枚举每一行进行初等行变换
    {
      if (i == j)
        continue;
      ll d = a[j][i] * div % MOD;
      // 这里循环开始的值不能写成 i, 矩阵 a 第 i 列之前都清零了可以省略，但矩阵 b 前面的列不能省略
      rep (k, 1, n)
      {
        a[j][k] = ((a[j][k] - a[i][k] * d % MOD) + MOD) % MOD;
        b[j][k] = ((b[j][k] - b[i][k] * d % MOD) + MOD) % MOD;
      }
    }
    rep (j, 1, n) // 最终要把 a 处理成单位矩阵，这里直接处理每行
    {
      a[i][j] = a[i][j] * div % MOD;
      b[i][j] = b[i][j] * div % MOD;
    }
  }
  rep (i, 1, n)
  {
    rep (j, 1, n)
      printf("%lld ", b[i][j]);
    printf("\n");
  }
  return 0;
}

下辈子一定好好学线代 QAQ