P4783 【模板】矩阵求逆

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define LL long long

#define N 405

using namespace std;

const int mod=1e9+7;

template<class T>inline void rd(T &x){

    x=0; short f=1; char c=getchar();

    while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();

    while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();

    x*=f;

}

int n,m;

int f[N][N<<1],r,ans;

inline int qpow(int x,int k){

    int ret=1;

    while(k){

        if(k&1) ret=1LL*ret*x%mod;

        x=1LL*x*x%mod; k>>=1;

    } return ret;

}

inline void Gauss(){

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

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

            if(f[j][i]){

                if(j!=i) for(int k=1;k<=m;k++) swap(f[i][k],f[j][k]);

                break;

            }

        if(!f[i][i]){puts("No Solution");exit(0);}

        r=qpow(f[i][i],mod-2);

        for(int j=i;j<=m;j++) f[i][j]=1LL*f[i][j]*r%mod;

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

            if(j!=i){

                r=f[j][i];

                for(int k=i;k<=m;k++)

                    f[j][k]=(f[j][k]-1LL*r*f[i][k]%mod+mod)%mod;

            }

    }

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

        for(int j=n+1;j<=m;j++) printf("%d ",f[i][j]);

        puts("");

    } return;

}

int main(){

    rd(n); m=n<<1;

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

        for(int j=1;j<=n;j++) rd(f[i][j]);

        f[i][n+i]=1;

    }

    Gauss();

    return 0;

}