矩阵乘法Ⅰ

大家好，欢迎来到IT知识分享网。

由于矩阵乘法是本蒟蒻自学的，只学到了一点点皮毛。

矩阵乘法大法大大的好。

说实话，矩阵乘法相较于其它的“数学”部分的知识点要友好太多了，毕竟，现在依然记得当年周老师花了一个晚上时间来证明费马小定理……

数学真他妈不是人玩的东西。但矩阵乘法至少没有那么阴间，个人观点。

如何计算矩阵乘法？举个例子：

官方语言是：

一个\(n\times m\)的矩阵\(A\)和一个\(m\times p\)的矩阵\(B\)，\(A\times B\)的结果\(C\)为：

\( C_{i,j}=\sum_{{1\le k\le m}} A_{ik}\times B_{kj} \)

意思就是第一个矩阵第\(i\)行和第二个矩阵第\(j\)列的元素相乘，作为结果的第\(i\)行第\(j\)列的元素。乘好之后矩阵规模为取第一个的行数第二个的列数。

一句话：前行后列

意思是第一个矩阵拿出的是某一行，第二个矩阵拿出的是某一列。这就要求两个相乘的矩阵，第一个的列数等于第二个的行数。

它的作用（目前我知道的作用）：可以加快某些简单递推式的计算，把原本\(O(n)\)的复杂度降到\(O(\log n)\)。

比如一个经典应用：

已知数列\(a\)满足\(a_i=a_{i-1}+a_{i-2}\)，其中\(a_1=a_2=1\)，给定不超过\(10^9\)的正整数\(n\),\(a_n\)%\((1^9+7)\)的值。

易得：

\(a_i=a_{i-1}+a_{i-2}\)

\(a_{i-1}=a_{i-1}\)

所以：

\( \begin{bmatrix} a_i\\ a_{i-1} \end{bmatrix}= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\times \begin{bmatrix} a_{i-1}\\ a_{i-2} \end{bmatrix} \)

又因为矩阵乘法满足结合律，所以：

\( \begin{bmatrix} a_n\\ a_{n-1} \end{bmatrix}= \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n-2}\times \begin{bmatrix} 1\\ 1 \end{bmatrix} \)

然后就可以用快速幂来做了

模板：斐波那契数列

#include<cstdio>
#define int long long
const int mod=1e9+7;

struct node{
	int a[3][3];
}newone;
inline node cheng(node s1,node s2){
	node re=newone;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++){
				re.a[i][j]+=s1.a[i][k]*s2.a[k][j];
				re.a[i][j]%=mod;
			}
		}
	}
	return re;
}
node qpow(node s1,int s2){
	if(s2==1)return s1;
	node re=qpow(s1,s2>>1);
	re=cheng(re,re);
	if(s2&1)re=cheng(re,s1);
	return re;
}

signed main(){
	
	int m;
	scanf("%lld",&m);
	node fir=newone;
	fir.a[1][1]=fir.a[1][2]=fir.a[2][1]=1;
	if(m<=2){
		printf("1");
		return 0;
	}
	node sm=qpow(fir,m-2);
	printf("%lld",(sm.a[1][1]+sm.a[1][2])%mod);
	
	return 0;
}

模板2：【模板】矩阵快速幂
AC代码：

#include<cstdio>
#define int long long
const int mod=1e9+7;
const int M=105;

int m;
struct node{
	int a[M][M];
}newone,fir;
inline node cheng(node s1,node s2){
	node re=newone;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=m;k++){
				re.a[i][j]+=s1.a[i][k]*s2.a[k][j];
				re.a[i][j]%=mod;
			}
		}
	}
	return re;
}
node qpow(node s1,int s2){
	if(s2==1)return s1;
	node re=qpow(s1,s2>>1);
	re=cheng(re,re);
	if(s2&1)re=cheng(re,s1);
	return re;
}

signed main(){
	
	int n;
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&fir.a[i][j]);
		}
	}
	node ans=qpow(fir,n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			printf("%lld ",ans.a[i][j]);
		}
		putchar('\n');
	}
	
	return 0;
}

个人建议把矩阵包装成结构体（如果矩阵不是很大的话），那么可以在主函数外面定义结构体的时候声明一个newone，省的在其它函数里面创一个矩阵还要麻烦地在那里初始化。