矩阵乘法是一种高效的算法可以把一些一维递推优化到log

《矩阵乘法是一种高效的算法可以把一些一维递推优化到log》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、矩阵运算是属于线性代数里的一个重要内容，上学期学完后只觉得矩阵能解线性方程，不过高屮的时候听说过矩阵能优化常系数递推以及将坐标上的点作线性变换，于是找了些资料研究了一下，并把许多经典题以及HDUsM崽大牛总结的矩阵乘法的题日［11、辺和开设的矩阵乘法DIYContest给做完了,感觉收获颇丰。一个矩阵就是一个二维数组，为了方便声明多个矩阵，我们一般会将矩阵封装一个类或定义一个矩阵的结构体，我采用的是后者：structMat{longlongmat[MAXN][MAXN];//

2、的元素为1,非对角线元素为Oofor(inti=0;i

3、)

4、

5、Iif(a.mat[i][k]&&b•脱t[k][j])c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;returnc;}矩阵加法就是简单地将对应的位置的两个矩阵的元素相加:Matope「日to厂+(MatajMatb){Matc;memset(c.matJ0Jsizeof(Mat));for(inti=0;i

6、是n阶方阵Z间的乘法以及n阶方阵与n维向量(把向量看成nxl的矩阵)的乘法。矩阵乘法最重要的性质就是满足结合律，同时它另一个很重要的性质就是不满足交换率，这保证了矩阵的幕运算满足快速幕啟模(AAk%MOD)算法:假设k=27,则k的二进制表示为11011,所以Ak=A11O11(2)_^1X2°+1X21+0X2z+23+24=A1XA2XA°XA8XA16=A1X(A1)2XEX(((A1)2)2)2X(((A1)2)2)2)2按二进制展开，乘以相应的权值,可以看出：k的二进制的每一位矩阵A都要平方，在k二进制为1的位：末矩阵x平方后的A,在k二进制为0的位

7、则末矩阵xE(单位矩阵)，即不变。代码如下：重载按位与(乘方)和加法时注意，加法的优先级高于按位与Matoperato「八(Matintx)//优先级低加括号{Matc；c=E；for(;x;x>>=1){if(x&1)c=c*A;A=A*A;许多题目还要求S=A+A2+A3+...+a'。其实再作一次二分即可：只需计算log(n)个A的幕即可。A+A2+屮++A5+A6=(A+A?+A3)x(^4-A3)将二分若A中=m表示从i到j有m条有向边，则A”中=n表示从i经过k条有向边到达j,这样的走法有n种Mat{sum(intx)//aai+aa2+...+a

8、axif(x==1)returnA;if(x&1)return(AAx)+sum(x-l);returnsum(x/2)*((AA(x/2))+E);矩阵在ACM里用处最大的就是加速常系数递推方程的计算，最经典的例子就是Fibonacci数列，如果普通的递推，计算笫n项复杂度为o(n),显然对于10人9左右的数据就力不从心了。如果用矩阵快速幕递推的话，计算第n项的复杂度为o卅*log(n)),对应一般的题目已经绰绰有余了，有的题目可以根据矩阵的特殊性进行优化，可以达到o(Z：2*log(n))o由f=af+bf常系数递推式右边有两项，所以向量和矩阵的规格都为2

9、o容JnJ/?-!Jn-2实现计算Fibonacci数列第k项的代码如下：constintMAXN=2;//矩阵规格constintMOD=100000000;//^intvec[MAXN]={1，IMatfib=1,0}；while(cin>>k&&k){ans=fibAk;intsum=0;for(inti=0;i

10、11、"一4V⑷、/@-1)1000X