题目大意: 给你一个矩阵 $A$, 求它的逆矩阵 $A^{-1}$, 使得 $AA^{-1}=I$
题解: 设 $A=IE_1E_2\cdots E_k$($E_i$ 为一个变换), 那么 $A^{-1}=E_k^{-1}E_{k-1}^{-1}\cdots E_{1}^{-1}$, 可以在 $A$ 变为 $I$ 的时候对 $I$ 做相同的操作. 当 $A$ 变为 $I$ 时,$I$ 就变成了 $A^{-1}$
卡点: 无
C++ Code:
- #include <algorithm>
- #include <cstdio>
- const int mod = 1e9 + 7;
- inline int pw(int base, int p) {
- static int res;
- for (res = 1; p; p>>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
- return res;
- }
- inline int inv(int x) { return pw(x, mod - 2); }
- inline void reduce(int &x) { x += x>> 31 & mod; }
- #define maxn 405
- int n, nn;
- int s[maxn][maxn <<1];
- int main() {
- scanf("%d", &n); nn = n + n;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= n; ++j) scanf("%d", s[i] + j);
- s[i][n + i] = 1;
- }
- for (int i = 1; i <= n; ++i) {
- int pos = i;
- while (pos <= n && !s[pos][i]) ++pos;
- if (pos> n) {
- puts("No Solution");
- return 0;
- }
- for (int j = i; j <= nn; ++j) std::swap(s[pos][j], s[i][j]);
- const int Inv = inv(s[i][i]);
- for (int j = i; j <= nn; ++j) s[i][j] = static_cast<long long> (s[i][j]) * Inv % mod;
- for (int j = 1; j <= n; ++j) if (i != j) {
- const int t = s[j][i];
- for (int k = i; k <= nn; ++k) reduce(s[j][k] -= static_cast<long long> (s[i][k]) * t % mod);
- }
- }
- for (int i = 1; i <= n; ++i) {
- for (int j = n + 1; j <= nn; ++j) printf("%d", s[i][j]);
- puts("");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2909403.html