Luogu4783 【模板】矩阵求逆（高斯消元）

　　对矩阵进行高斯消元直至消为单位矩阵，并在另一个单位矩阵上对其做同样的操作即可。

　　模意义下的高斯消元可以直接计算系数来避免整行的辗转相除。

　　还不知道有什么用。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000007

#define N 410

int n,a[N][N],b[N][N];

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int ksm(int a,int k)

{

    if (k==) return ;

    int tmp=ksm(a,k>>);

    if (k&) return 1ll*tmp*tmp%P*a%P;

    else return 1ll*tmp*tmp%P;

}

int inv(int a){return ksm(a,P-);}

void gauss()

{

    for (int i=;i<n;i++)

    {

        if (!a[i][i])

        for (int j=i+;j<=n;j++)

        if (a[j][i]) {swap(a[i],a[j]),swap(b[i],b[j]);break;}

        for (int j=i+;j<=n;j++)

        if (a[j][i])

        {

            int x=a[j][i]/gcd(a[i][i],a[j][i]),y=a[i][i]/gcd(a[i][i],a[j][i]);

            for (int k=;k<=n;k++)

            a[j][k]=(1ll*a[j][k]*y%P-1ll*a[i][k]*x%P+P)%P,

            b[j][k]=(1ll*b[j][k]*y%P-1ll*b[i][k]*x%P+P)%P;

        }

    }

    if (a[n][n])

    {

        for (int i=;i<=n;i++)

        b[n][i]=1ll*b[n][i]*inv(a[n][n])%P;

        a[n][n]=;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++)

        for (int j=;j<=n;j++)

        a[i][j]=read(),b[i][j]=(i==j);

    gauss();

    for (int i=;i<=n;i++) if (a[i][i]==) {cout<<"No Solution";return ;}

    for (int i=n;i>;i--)

        for (int j=i-;j>=;j--)

        if (a[j][i])

        {

            int x=a[j][i]/gcd(a[i][i],a[j][i]),y=a[i][i]/gcd(a[i][i],a[j][i]);

            for (int k=;k<=n;k++)

            a[j][k]=(1ll*a[j][k]*y%P-1ll*a[i][k]*x%P+P)%P,

            b[j][k]=(1ll*b[j][k]*y%P-1ll*b[i][k]*x%P+P)%P;

        }

    for (int i=;i<=n;i++)

        for (int j=;j<=n;j++)

        b[i][j]=1ll*b[i][j]*inv(a[i][i])%P;

    for (int i=;i<=n;i++)

    {

        for (int j=;j<=n;j++)

        printf("%d ",b[i][j]);

        printf("\n");

    }

    return ;

}