求一个N×N的矩阵的逆矩阵。答案对10^9+7取模。
输入格式
第一行有一个整数NN，代表矩阵的大小；
从第22行到第N+1行，每行N个整数，其中第i+1行第j列的数代表矩阵中的元素 a i j a_{ij} aij​。
输出格式
若矩阵可逆，则输出N行，每行N个整数，其中第ii行第jj列的数代表逆矩阵中的元素 b i j b_{ij} bij​，答案对10^9+7取模；否则只输出一行 No Solution。
输入

3
1 2 8
2 5 6
5 1 2

输出

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503

输入

3
3 2 4
7 2 9
2 4 3

输出

No Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f,mod=1e9+7,MAXN=5;
ll qpow(ll x,ll k){
    ll res=1;
    while(k){
        if(k&1)res=res*x%mod;
        x=x*x%mod;k>>=1;
    }return res;
}
ll a[MAXN][MAXN<<1];
int n;
bool gauss(){//求矩阵的逆，a换成a[MAXN][MAXN+1]则求解方程的解。
    for(int i=1,r=1;i<=n;r=++i){
        for(int j=i+1;j<=n;++j)if(a[j][i]>a[r][i])r=j;//找第i行下面第i列最大的元素
        if(a[r][i]==0)return 0;//最大元素==0，矩阵非奇异
        if(i^r)for(int j=1;j<=n<<1;++j)swap(a[i][j],a[r][j]);//交换r，i行
        ll inv=qpow(a[i][i],mod-2);//第i，i个元素的逆元
        for(int j=i;j<=n<<1;++j)a[i][j]=inv*a[i][j]%mod;
        //第i行其他元素除以第i，i个元素
        for(int k=1;k<=n;++k){//第k行
            if(k==i)continue;
            ll p=a[k][i];//不能带入，因为j==i时把a[k][i]改了
            //row(j)减去p*row(i)
            for(int j=i;j<=n<<1;++j)a[k][j]=(a[k][j]-p*a[i][j]%mod+mod)%mod;
        }
    }
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        a[i][n+i]=1;//单位矩阵
        for(int j=1;j<=n;++j)scanf("%lld",&a[i][j]);
    }
    if(!gauss())printf("No Solution");
    else for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)printf("%lld ",a[i][n+j]);
        printf("\n");
    }
    return 0;
}