题解 P4783 【【模板】矩阵求逆】

# 矩阵求逆 在线性代数里面，向量通过某个函数发生变化，从而生成另一个向量。 那个函数即对应着一种坐标轴的变换，通过坐标轴的变换，影响了向量的基底，而又因为坐标轴的变换，其他所有向量的变换方式皆与向量基底相同，那么我们可以根据基底的变换方式，理解矩阵乘法的本质 那么对于向量的坐标变换,就可以看做是一组向量乘一个变换方式，即两个矩阵相乘，而使变换后的向量通过与原变换相反的一次变换，就可以得到原来初始基底 讲了这么多，其实就是把初始向量 $\begin{bmatrix}1&0\\0&1\\\end{bmatrix}$ 经过变换之后，变成了一格矩阵 $\begin{bmatrix}3&2\\4&6\\\end{bmatrix}$ 那么对于任意的一组向量 $\begin{bmatrix}3\\5\\\end{bmatrix}$ , 我们也可以把它进行这个变换， 即$\begin{bmatrix}3&2\\4&6\\\end{bmatrix}$ $*$ $\begin{bmatrix}2\\3\\\end{bmatrix}$ $=$ $\begin{bmatrix}12\\26\\\end{bmatrix}$ 然后我们根据把向量反向变换，就可以知道矩阵的逆了 或者说，矩阵$A*A^{-1}=E$,即矩阵乘它的逆就为单位矩阵 我们可以根据高斯消元来求出一个上三角矩阵，当我们在不断把原矩阵消为上三角矩阵时，我们得到的另一个矩阵即为它的逆 Code ``` #include<bits/stdc++.h> using namespace std; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } const int N=405,mod=1e9+7; int n; struct Matrix { int a[N][N]; void Swap(int x,int y) {for(int i=1;i<=n;++i) swap(a[x][i],a[y][i]);} void cg(int x,int k) {for(int i=1;i<=n;++i) a[x][i]=(1ll*a[x][i]*k%mod+mod)%mod;} void update(int x,int y,int k) {for(int i=1;i<=n;++i)a[x][i]=((a[x][i]+(1ll*a[y][i]*k%mod))%mod+mod)%mod;} void print() {for(int i=1;i<=n;++i) {for(int j=1;j<=n;++j) printf("%d ",a[i][j]);printf("\n");}} }A,B; inline int inv(int a) { int res=1,b=mod-2; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod; return res; } int main() { n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) A.a[i][j]=read(); for(int i=1;i<=n;++i) B.a[i][i]=1; for(int i=1;i<=n;++i) { if(!A.a[i][i]) { for(int j=i+1;j<=n;++j) if(A.a[j][i]) {A.Swap(i,j),B.Swap(i,j);break;} } if(!A.a[i][i]) {printf("No Solution\n");return 0;} B.cg(i,inv(A.a[i][i])),A.cg(i,inv(A.a[i][i])); for(int j=i+1;j<=n;++j) B.update(j,i,-A.a[j][i]),A.update(j,i,-A.a[j][i]); } for(int i=n-1;i;--i) for(int j=i+1;j<=n;++j) B.update(i,j,-A.a[i][j]),A.update(i,j,-A.a[i][j]); B.print(); } ``` 感谢[BZT巨佬](https://www.luogu.org/space/show?uid=41781)的讲解 ~~深深感觉到自己的弱小~~