Luogu 4783 矩阵求逆

Posted on | Views:

矩阵求逆板子.

  • 对一个矩阵,定义它的三种初等行变换:
  1. 交换某两行.
  2. 将某一行的元素全部 $\times k (k\not= 0)$ .
  3. 将某一行的元素的 $k$ 倍加到另一行对应位置上去.
  • 每个初等行变换都对应了一个初等矩阵,即,对矩阵 $A$ 做一次初等行变换,等价于用对应的初等矩阵 $P_0$ 左乘 $A$ ,即 $A=P_0A$ .
  • 若矩阵 $A$ 有逆,一定可以通过高斯消元,做有限次初等行变换得到单位矩阵 $I$ .即, $P_kP_{k-1}\dots P_0 A=I$ .根据矩阵乘法的结合律,把前面所有 $P_i$ 看做一个矩阵 $P$ ,即 $PA=I$ ,根据定义, $P$ 就是我们要求的 $A^{-1}$ .
  • 而 $PI=P$ ,所以我们再维护一个矩阵 $B$ ,初始为 $I$ ,高斯消元时同步与 $A$ 做相同的初等行变换,当 $A$ 变为 $I$ 时, 得到的 $B$ 就是我们要求的 $P$ ,即 $A^{-1}$ .
  • 若在高斯消元时发现 $A$ 无法消成 $I$ ,则说明 $A$ 不可逆.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
int add(int a,int b)
{
	return (a + b) % P;
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=400+10;
int n,A[MAXN][MAXN],B[MAXN][MAXN];
void addrow(int a[],int b[],int t)
{
	for(int i=1;i<=n;++i)
		a[i]=add(a[i],mul(b[i],t));
}
bool inverse()
{
	for(int i=1;i<=n;++i)
		B[i][i]=1;
	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 false;
		int inv=fpow(A[i][i],P-2);
		for(int j=i+1;j<=n;++j)
		{
			int x=A[j][i];
			addrow(A[j],A[i],P-mul(x,inv));
			addrow(B[j],B[i],P-mul(x,inv));
		}
	}
	for(int i=n;i>=1;--i)
	{
		int inv=fpow(A[i][i],P-2);
		for(int j=1;j<i;++j)
		{
			int x=A[j][i];
			addrow(A[j],A[i],P-mul(x,inv));
			addrow(B[j],B[i],P-mul(x,inv));
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(!A[i][i])
			return false;
		int inv=fpow(A[i][i],P-2);
		for(int j=1;j<=n;++j)
			B[i][j]=mul(B[i][j],inv);	
	}
	return true;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			A[i][j]=read();
	if(inverse())
	{
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
				printf("%d ",B[i][j]);
			puts("");
		}
	}
	else
		puts("No Solution");
	return 0;
}