专栏文章

P4783 【模板】矩阵求逆 题解

SSatellite_system
P4783题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6ouwv
此快照首次捕获于
2025/12/01 21:27
3 个月前
此快照最后确认于
2025/12/01 21:27
3 个月前
查看原文

题面解释：

给出矩阵 AA，求出 AA 的逆矩阵，即 A−1A^{-1}。

思路分析：

前置知识：高斯消元。
逆矩阵是什么呢？我们知道 aa 逆元是 a−1a^{-1}，而 a×a−1=1a\times a^{-1}=1，这里的 11 可以理解为“单位 11”。而我们有单位矩阵 II 为主对角线上都为 11，其余都为 00。之所以这样定义，是因为 II 与 11 有共同的性质就是与之做乘法不改变原矩阵或数。
所以对比数的式子，有 A×A−1=IA\times A^{-1}=I。将矩阵扩容一下，我们可以构造出 [AI][AI]，有 [AI]×A−1=[IA−1][AI]\times A^{-1}=[IA^{-1}]，发现形式很熟悉呀，这就转换成了高斯消元的问题。（注：其中 [AI][AI] 表示把 AA 和 II 两个矩阵横向拼接，[IA−1][IA^{-1}] 同理）。
高斯消元后直接输出即可，判断无解的方式也不变。

AC Code:

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=810,mod=1e9+7;
int n,a[N][N];
int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1)res=res*x%mod;
		x=x*x%mod,y>>=1;
	}
	return res;
}
void gauss(){
	for(int i=1,k=1;i<=n;k=++i){
		for(int j=i+1;j<=n;j++)
			if(a[j][i])k=j;
		for(int j=1;j<=2*n;j++)
			swap(a[i][j],a[k][j]);
		if(!a[i][i])return printf("No Solution"),void();
		for(int j=1,tmp=a[i][i];j<=2*n;j++)
			a[i][j]=a[i][j]*qpow(tmp,mod-2)%mod;
		for(int k=1;k<=n;k++)if(k!=i)
			for(int l=1,tmp=a[k][i];l<=2*n;l++)
				a[k][l]=(a[k][l]-a[i][l]*tmp%mod+mod)%mod;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cout<<a[i][j+n]<<" \n"[j==n];
	return;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n&&(a[i][i+n]=1);i++)
		for(int j=1;j<=n;j++)cin>>a[i][j];
	gauss();
	return 0;
}
完结撒花！！！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...