题目链接:https://www.luogu.org/problemnew/show/P4783
时空限制 1000ms / 128MB

题目描述

求一个N×N的矩阵的逆矩阵。答案对10^9+7取模。

输入格式

第一行有一个整数N，代表矩阵的大小;
从第2行到第N+1行，每行N个整数，其中第i+1行第j列的数代表矩阵中的元素。

输出格式

若矩阵可逆，则输出NN行，每行NN个整数，其中第ii行第jj列的数代表逆矩阵中的元素 ​，答案对10^9+7取模;
否则只输出一行 No Solution。

输入样例

3
1 2 8
2 5 6
5 1 2
3
3 2 4
7 2 9
2 4 3

输出样例

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503
No Solution

说明

对30%的数据有N≤100;
对100%的数据有N≤400，所有<10^9+7。
ps.TLE的同学可以试试大力卡常，标算不开O2勉强能卡过去的

解题思路

学过线性代数的同学应该知道:对于一个矩阵A，A可逆的充分必要条件是A经过若干次初等行变换可以变成E(即单位矩阵)，即存在一个矩阵P使得PA=E，则P=.

考虑怎么求出P，如果我们同时维护两个矩阵A,B，令B一开始时等于E，在把A变为E的过程中对B也做相等的初等变换，那么当A变为E时，B也就变为了P(因为做初等行变换等价于被对应的初等矩阵左乘), 即:

通过初等行变换使得A变为E并不困难，可以用高斯消元解决，先消成上三角矩阵，然后再消成对角矩阵.
如果在高斯消元的过程中发现无法将A变为E，输出无解即可.

不会高斯的请看这里~, 求逆矩阵的时候还会用到逆元，不会逆元的请看这里~.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 1e9 + 7;
ll a[405][805];
ll inv(ll a, ll b, ll p) {
    ll cnt = 1;
    while (b) {
        if (b & 1)
            cnt = cnt * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return cnt;
}
void Gauss(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (a[j][i]) {
                for (int k = 1; k <= n << 1 && !a[i][i]; k++)
                    swap(a[i][k], a[j][k]);
            }
        }
        if (!a[i][i]) {
            puts("No Solution");
            return ;
        }
        ll inv_ = inv(a[i][i], p - 2, p);
        for (int j = i; j <= n << 1; j++)
            a[i][j] = a[i][j] * inv_ % p;
        for (int j = 1; j <= n; j++) {
            if (j != i) {
                ll m = a[j][i];
                for (int k = i; k <= n << 1; k++)
                    a[j][k] = (a[j][k] - m * a[i][k] % p + p) % p;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= n << 1; j++)
            printf("%lld ", a[i][j]);
        printf("\n");
    }
}
int main() {
    int n;
    scanf("%d", &n);
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            scanf("%lld", &a[i][j]);
        a[i][n + i] = 1;
    }
    Gauss(n);
    return 0;
}