【模板】矩阵求逆（矩阵初等变换）
O(n5)O(n^5)O(n5) 做法：
先求出 AAA 的伴随矩阵 A∗A^{*}A∗，后利用 A∗A∗=∣A∣∗E⇒A−1=A∗∣A∣A*A^{*}=|A|*E\Rightarrow A^{-1}=\frac{A^{*}}{|A|}A∗A∗=∣A∣∗E⇒A−1=∣A∣A∗ 求解需要求 O(n2)O(n^2)O(n2) 次行列式
O(n4)O(n^4)O(n4) 做法：
对每一行来一波高斯消元O(n3)O(n^3)O(n3) 做法：
首先介绍矩阵的初等变换（以下为初等行变换）：
引入：初等矩阵： 把单位矩阵 EEE 经过一次初等变换得到的矩阵称为初等矩阵。
性质1：设 AAA 为 m×nm\times nm×n矩阵，对 AAA 进行一次初等行变换相当于在 AAA 的左边乘上对应的 mmm 阶初等矩阵
性质2：方阵 AAA 可逆的充分必要条件是存在有限个初等矩阵 P1,P2,...,PlP_1,P_2,...,P_lP1,P2,...,Pl 使 A=P1P2...PlA=P_1P_2...P_lA=P1P2...Pl
充分性：因为初等矩阵均可逆，所以有限个初等矩阵的乘积仍可逆，故 AAA 可逆。
必要性：设 AAA 可逆，它经过有限次初等行变换变为行最简矩阵 BBB，那么存在初等矩阵 Q1,Q2,...,QlQ_1,Q_2,...,Q_lQ1,Q2,...,Ql 使 Q1Q2...QlA=BQ_1Q_2...Q_lA=BQ1Q2...QlA=B，因为 A,QiA,Q_iA,Qi 均可逆，故 BBB 可逆，故 ∣B∣≠0,B=E|B|\neq 0,B=E∣B∣=0,B=E
此时 A=Q1−1Q2−1...Ql−1B=Q1−1Q2−1...Ql−1=P1...PlA=Q_1^{-1}Q_2^{-1}...Q_l^{-1}B=Q_1^{-1}Q_2^{-1}...Q_l^{-1}=P_1...P_lA=Q1−1Q2−1...Ql−1B=Q1−1Q2−1...Ql−1=P1...Pl，此时 Pi=Qi−1P_i=Q_i^{-1}Pi=Qi−1为初等矩阵
定理证明：A∼B⇔A\sim B \LeftrightarrowA∼B⇔ 存在有限个矩阵 P1,P2,...,PlP_1,P_2,...,P_lP1,P2,...,Pl 使 Pl...P2P1A=B⇔P_l...P_2P_1A=B \LeftrightarrowPl...P2P1A=B⇔ 存在可逆矩阵 PPP使 PA=BPA=BPA=B
推论：方阵 AAA 可逆的充分必要条件是 A∼EA\sim EA∼E
证明：AAA 可逆 ⇔\Leftrightarrow⇔ 存在可逆矩阵 PPP，使 PA=E⇔A∼EPA=E\Leftrightarrow A\sim EPA=E⇔A∼E
本题解法：现在知道 AAA，求 PPP 使 PA=EPA=EPA=E
同时我们有 PE=EPE=EPE=E，那么我们有 P(A,E)=(E,P)P(A,E)=(E,P)P(A,E)=(E,P)，于是我们对矩阵 (A,E)(A,E)(A,E) 做初等行变换，当 AAA 变为 EEE 时，EEE 就变成了 PPP，无解情况用推论判断即可，复杂度 O(n3)O(n^3)O(n3)，非常好写
#include
#define cs const
using namespace std;
int read(){
int cnt = 0, f = 1; char ch = 0;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }
while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
return cnt * f;
}
cs int Mod = 1e9 + 7;
typedef long long ll;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b =Mod?r%Mod:r; }
int ksm(int a, int b){ int as=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) as=mul(as,a); return as; }
void Add(int &a, int b){ a = add(a, b); }
void Mul(int &a, int b){ a = mul(a, b); }
void Dec(int &a, int b){ a = dec(a, b); }
cs int N = 405, M = N + N;
#define poly vector
int n; poly a[N];
poly operator - (poly a, poly b){
for(int i=1; i<=n+n; i++) Dec(a[i],b[i]); return a;
}
poly operator * (poly a, int coe){
for(int i=1; i<=n+n; i++) Mul(a[i],coe); return a;
}
int main(){
n = read();
for(int i = 1; i <= n; i++){
a[i].resize(n+n+1);
for(int j = 1; j <= n; j++) a[i][j] = read();
}
for(int i = 1; i <= n; i++) a[i][i+n] = 1;
for(int i = 1; i <= n; i++){
int k = i;
for(int j = i+1; j <= n; j++) if(a[j][i]){ k = j; break; }
if(i ^ k) swap(a[i], a[k]);
int iv = ksm(a[i][i], Mod-2);
for(int j = i+1; j = 1; i--){
if(a[i][i] == 0){ puts("No Solution"); return 0; }
for(int j = i+1; j <= n; j++) if(a[i][j]) a[i] = a[i] - a[j] * a[i][j];
int iv = ksm(a[i][i],Mod-2); a[i] = a[i] * iv;
}
for(int i = 1; i <= n; i++){
for(int j = n+1; j <= n+n; j++) cout << a[i][j] << " ";
puts("");
} return 0;
}
作者：FSYo
