P4783 【模板】矩阵求逆

根据线性代数里面的做法，我们构造一个增广矩阵 $[A,E]$ ，两端施加一个操作 $P$ ，当 $[PA,PE]=[E,PE]$ 的时候， $P$ 就是 $E^{-1}$ 。我们可以通过矩阵的初等行变换完成上述的内容，核心就是 1. 交换两行，2. 把一行的 $k$ 倍加到另一行还有一种操作不属于矩阵的初等行变换，就是一行乘以一个常数。

#include <bits/stdc++.h>
#define MAXN 1005
#define MOD 1000000007
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int a[MAXN][MAXN*2];
int n;
int ksm(int b,int k){
	int res=1;
	while(k){
		if(k&1) res=1LL*res*b%MOD;
		b=1LL*b*b%MOD;
		k>>=1;
	}
	return res;
}
int rev(int b){
	return ksm(b,MOD-2);
}
namespace Gauss_Inv{
	void Gauss(){
		for (int i=1;i<=n;++i){//将第i行看成主元
			int r=i;
			for (int j=i+1;j<=n;++j){
				if (abs(a[j][i])>abs(a[r][i])) r=j;
			}
			for (int j=1;j<=n*2;++j) swap(a[i][j],a[r][j]);//交换的操作是为了尽可能让 a[i][i]=0
			if (a[i][i]==0){//矩阵不是满秩矩阵
				puts("No Solution");
				exit(0);
			}
			int inv=rev(a[i][i]);
			for (int j=1;j<=n;++j){
				if (j==i) continue;
				int t=1LL*a[j][i]*inv%MOD;
				for (int k=1;k<=n*2;++k){
					a[j][k]=(a[j][k]-1LL*a[i][k]*t%MOD+MOD)%MOD;
				}
			}
		}
		for (int i=1;i<=n;++i){
			int inv=rev(a[i][i]);
			for (int j=1;j<=2*n;++j){
				a[i][j]=1LL*a[i][j]*inv%MOD;
			}
		}
	}
};
using namespace Gauss_Inv;
int main(){
	n=read();
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			a[i][j]=read();
			a[i][j+n]=i==j;
		}
	}
	Gauss();
	for (int i=1;i<=n;++i){
		for (int j=1;j<=n;++j){
			printf("%d ",a[i][j+n]);
		}
		puts("");
	}
	return 0;
}