P4783 【模板】矩阵求逆 题解

· · 题解

题面解释：

给出矩阵 A，求出 A 的逆矩阵，即 A^{-1}。

思路分析：

前置知识：高斯消元。

逆矩阵是什么呢？我们知道 a 逆元是 a^{-1}，而 a\times a^{-1}=1，这里的 1 可以理解为“单位 1”。而我们有单位矩阵 I 为主对角线上都为 1，其余都为 0。之所以这样定义，是因为 I 与 1 有共同的性质就是与之做乘法不改变原矩阵或数。

所以对比数的式子，有 A\times A^{-1}=I。将矩阵扩容一下，我们可以构造出 [AI]，有 [AI]\times A^{-1}=[IA^{-1}]，发现形式很熟悉呀，这就转换成了高斯消元的问题。（注：其中 [AI] 表示把 A 和 I 两个矩阵横向拼接，[IA^{-1}] 同理）。

高斯消元后直接输出即可，判断无解的方式也不变。

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=810,mod=1e9+7;
int n,a[N][N];
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod,y>>=1;
    }
    return res;
}
void gauss(){
    for(int i=1,k=1;i<=n;k=++i){
        for(int j=i+1;j<=n;j++)
            if(a[j][i])k=j;
        for(int j=1;j<=2*n;j++)
            swap(a[i][j],a[k][j]);
        if(!a[i][i])return printf("No Solution"),void();
        for(int j=1,tmp=a[i][i];j<=2*n;j++)
            a[i][j]=a[i][j]*qpow(tmp,mod-2)%mod;
        for(int k=1;k<=n;k++)if(k!=i)
            for(int l=1,tmp=a[k][i];l<=2*n;l++)
                a[k][l]=(a[k][l]-a[i][l]*tmp%mod+mod)%mod;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cout<<a[i][j+n]<<" \n"[j==n];
    return;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n&&(a[i][i+n]=1);i++)
        for(int j=1;j<=n;j++)cin>>a[i][j];
    gauss();
    return 0;
}

完结撒花！！！