【模板】矩阵求逆

P4783 【模板】矩阵求逆

题目描述

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

---

在原矩阵右边接一个单位矩阵，然后把原矩阵通过初等变换消成单位矩阵，右边的单位矩阵做同样的变换，就成了逆矩阵。

什么，为什么？

难得你不觉得这个想起来非常的正确么

---

Code:

// luogu-judger-enable-o2
#include <cstdio>
#include <algorithm>
#include <cctype>
const int mod=1e9+7;
const int N=810;
int n,a[N][N];
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
#define mul(a,b) (1ll*(a)*(b)%mod)
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
int read()
{
    int x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            a[i][j]=read();
        a[i][i+n]=1;
    }
    for(int i=1;i<=n;i++)
    {
        int id=-1;
        for(int j=i;j<=n;j++) if(a[j][i]) {id=j;break;}
        if(id==-1) return puts("No Solution"),0;
        std::swap(a[i],a[id]);
        int inv=qp(a[i][i],mod-2);
        for(int j=i;j<=n<<1;j++) a[i][j]=mul(a[i][j],inv);
        for(int j=i+1;j<=n;j++)
            for(int k=n<<1;k>=i;k--)
                a[j][k]=add(a[j][k],mod-mul(a[i][k],a[j][i]));
    }
    for(int i=n;i;i--)
        for(int j=i-1;j;j--)
            for(int k=n<<1;k>=i;k--)
                a[j][k]=add(a[j][k],mod-mul(a[i][k],a[j][i]));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",a[i][j+n]);
        puts("");
    }
    return 0;
}

---

2019.2.15