P4783 【模板】矩阵求逆
题目描述
求一个$N imes N$的矩阵的逆矩阵。答案对$10^9+7$取模。
输入输出格式
输入格式：第一行有一个整数$N$，代表矩阵的大小；
从第$2$行到第$N+1$行，每行$N$个整数，其中第$i+1$行第$j$列的数代表矩阵中的元素$a_{ij}$。
输出格式：若矩阵可逆，则输出$N$行，每行$N$个整数，其中第$i$行第$j$列的数代表逆矩阵中的元素 $b_{ij}$，答案对$10^9+7$取模；
否则只输出一行 No Solution。
输入输出样例
3 1 2 8 2 5 6 5 1 2
718750005 718750005 968750007 171875001 671875005 296875002 117187501 867187506 429687503
说明
对30%的数据有$Nle 100$；
对100%的数据有$Nle 400$，所有$a_{ij}<10^9+7$。
ps.TLE的同学可以试试大力卡常，标算不开O2勉强能卡过去的
bztMinamoto的题解
定义矩阵的三种初等行变换：
-
交换某两行。
-
将某一行的所有元素乘上(k)((k eq 0))。
-
将某一行的所有元素乘上(k)加到另一行去。
每一个初等变换都对应一个初等矩阵，即矩阵(A)做某一线性变换等价于用一个对应的初等矩阵左乘(A)。若有一堆初等变换(1,2,...l)，对应的初等矩阵分别为(P_1,P_2,...,P_l)，那么经过这些线性变换后的矩阵即为(P_l....P_2P_1A=PA)（(P)为之前那堆东西的乘积）。
对于一个矩阵(A)，(A)可逆的充分必要条件是(A)经过若干次初等行变换可以变成(E)（(E)即单位矩阵），即存在一个矩阵(P)使得(PA=E)，则(P=A^{-1})。
通过初等行变换使得(A)变为(E)并不困难，可以用高斯消元解决，先消成上三角矩阵，然后再消成对角矩阵。
考虑怎么求出(P)，因为有(PA=E,PE=P)，如果我们同时维护两个矩阵(A,B)，令(B)一开始时等于(E)，在把(A)变为(E)的过程中对(B)也做相等的初等变换，那么当(A)变为(E)时，(B)也就变为了(P)（因为做初等行变换等价于被对应的初等矩阵左乘）。
如果在高斯消元的过程中发现无法将(A)变为(E)，输出无解即可。(O(n^3))。
注意为了卡常我们可以只对(A)的下三角消元，但是不能对(B)这样做，道理显然。
#include<bits/stdc++.h>
#define co const
#define il inline
using namespace std;
typedef long long LL;
co int mod=1000000000+7;
il int add(int a,int b){
return (a+=b)>=mod?a-mod:a;
}
il int mul(int a,int b){
return (LL)a*b%mod;
}
int fpow(int a,int b){
int ans=1;
for(;b;b>>=1,a=mul(a,a))
if(b&1) ans=mul(ans,a);
return ans;
}
co int N=401;
int n,a[N][N],b[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;b[i][i]=1,++i)
for(int j=1;j<=n;++j) scanf("%d",a[i]+j);
for(int i=1;i<=n;++i){
if(!a[i][i]){
for(int j=i+1;j<=n;++j)
if(a[j][i]) {swap(a[i],a[j]),swap(b[i],b[j]);break;}
}
if(!a[i][i]) return puts("No Solution"),0;
int inv=fpow(a[i][i],mod-2);
for(int k=1;k<=n;++k) a[i][k]=mul(a[i][k],inv),b[i][k]=mul(b[i][k],inv); // edit !:do all
for(int j=1;j<=n;++j)if(j!=i){
int coef=a[j][i];
for(int k=1;k<=n;++k) a[j][k]=add(a[j][k],mod-mul(coef,a[i][k])),b[j][k]=add(b[j][k],mod-mul(coef,b[i][k]));
}
}
for(int i=1;i<=n;puts(""),++i)
for(int j=1;j<=n;++j) printf("%d ",b[i][j]);
return 0;
}