洛谷P4783 【模板】矩阵求逆(高斯消元)
程序员文章站
2022-12-22 18:35:05
题意 "题目链接" Sol 首先在原矩阵的右侧放一个单位矩阵 对左侧的矩阵高斯消元 右侧的矩阵即为逆矩阵 cpp // luogu judger enable o2 include define LL long long using namespace std; const int MAXN = 2 ......
题意
sol
首先在原矩阵的右侧放一个单位矩阵
对左侧的矩阵高斯消元
右侧的矩阵即为逆矩阵
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 2001, mod = 1e9 + 7; const double eps = 1e-9; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[maxn][maxn]; int mul(int x, int y) { return 1ll * x * y % mod; } int fp(int a, int p) { int base = 1; while(p) { if(p & 1) base = mul(base, a); a = mul(a, a); p >>= 1; } return base; } int inv(int x) { return fp(x, mod - 2); } void add2(int &x, int y) { if(x + y < 0) x = x + y + mod; else x = (x + y >= mod) ? x + y - mod : x + y; } int matrixinv() { for(int i = 1; i <= n; i++) a[i][i + n] = 1; for(int i = 1; i <= n; i++) { int mx = i; for(int j = i + 1; j <= n; j++) if(a[j][i] > a[i][i]) mx = j; if(mx != i) swap(a[i], a[mx]); if(!a[i][i]) return -1; int inv = inv(a[i][i]); for(int j = i; j <= 2 * n; j++) a[i][j] = mul(a[i][j], inv); for(int j = 1; j <= n; j++) { if(i != j) { int r = a[j][i]; for(int k = i; k <= 2 * n; k++) add2(a[j][k], -mul(a[i][k], r)); } } } return 0; } signed main() { //freopen("testdata.in", "r", stdin); n = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = read(); if(matrixinv() == -1) {puts("no solution"); return 0;} for(int i = 1; i <= n; i++, puts("")) for(int j = n + 1; j <= 2 * n; j++) printf("%d ", a[i][j]); return 0; } /* 1 4 2 0 1 0 50 50 */
上一篇: 局部内部类访问它所在方法的局部变量时,要求该局部变量必须声明为final的原因
下一篇: 吃完饭