矩阵乘法总结.docx

矩阵乘法总结.docx

《矩阵乘法总结.docx》由会员分享，可在线阅读，更多相关《矩阵乘法总结.docx（4页珍藏版）》请在冰点文库上搜索。

矩阵乘法总结

2015.7.28矩阵乘法总结

矩阵，其实可以看成一个由m*n个元素组成的m行n列的二维数组：

矩阵可以进行一些运算：

加法减去乘法。

加法减法：

两个矩阵AB大小必须相同才可以进行运算，得到的矩阵C大小与矩阵AB的大小相同，其中Cij=Aij+（-）Bij，加法可以满足结合律和交换律。

乘法：

两个矩阵A（n1*m1）和B（n2*m2），必须满足m1=n2才可以进行运算,得到的矩阵C大小为n1*m2，其中Cij=∑Aik+Bkj（），也就是A矩阵的第i行与B矩阵的第j列相乘的累加。

矩阵乘法有很多奇妙的用法，与快速幂结合起来可以巧妙解决一些递推、dp的题目。

下面举一些例子

【斐波拉切数列】

输出斐波拉切数列的第n个数模10000007，其中0

用f[i]=f[i-1]+f[i-2]的方法时间复杂度为O（n），会超时。

假设f[i]和f[i+1]组成一个1*2的矩阵，如果要生成下一个并保存f[i+1]，则需要乘一个

01

11的矩阵。

而这样不断生成下去，就要不断乘以这个矩阵，这时就要运用到快速幂了，矩阵的快速幂和整数的快速幂一样，也是用二分的方法。

这种方法的时间复杂度为O（logN*2^3）。

【MatrixPowerSeries】

给出一个n*n的矩阵和一个正整数k，求A+A2+A3+…+Ak.的和模m。

n≤30k≤109m<104

设f[i]=A2+A3+…+Ai

直接做Ak是不行的，我们同样采用二分的方法。

如果i是奇数，那么f[i]=f[i/2]+f[i/2]*Ai、2+Ai

如果i是偶数，那么f[i]=f[i/2]+f[i/2]*Ai、2

这样问题就解决了。

程序：

#include

#include

#include

#include

#include

#include

usingnamespacestd;

structMat

{

intM[32][32];

intn,m;

Mat（）{memset（M,0,sizeof（M））;}

};

intMOD;

longlongK;

Matma,ans,f,P;

Matad（MatA,MatB）

{

Matret;

ret.n=A.n;

ret.m=A.m;

for（inti=1;i<=A.n;++i）

for（intj=1;j<=A.m;++j）

ret.M[i][j]=（A.M[i][j]+B.M[i][j]）%MOD;

returnret;

}

Matmul（MatA,MatB）

{

Matret;

ret.n=A.n;

ret.m=B.m;

for（inti=1;i<=A.n;++i）

for（intj=1;j<=B.m;++j）

{

ret.M[i][j]=0;

for（intk=1;k<=A.m;++k）

ret.M[i][j]=（ret.M[i][j]+（（A.M[i][k]%MOD）*（B.M[k][j]%MOD））%MOD）%MOD;

}

returnret;