矩阵乘法入门.docx

矩阵运算是属于线性代数里的一个重要内容，上学期学完后只觉得矩阵能解线性方程，不过高中的时候听说过矩阵能优化常系数递推以及将坐标上的点作线性变换，于是找了些资料研究了一下，并把许多经典题以及HDU shǎ崽大牛总结的矩阵乘法的题目/forum/read.php?tid=15908[1]、[2]和开设的矩阵乘法DIY Contest给做完了，感觉收获颇丰。 一个矩阵就是一个二维数组，为了方便声明多个矩阵，我们一般会将矩阵封装一个类或定义一个矩阵的结构体，我采用的是后者： 最特殊的矩阵应该就是单位矩阵E了，它的对角线的元素为1，非对角线元素为0。 若A为n×p矩阵，B为p×m矩阵，则它们的乘积AB(有时记做A·B)将是一个n×m矩阵。其乘积矩阵AB的第i行第j列的元素为： 一般矩阵乘法采用朴素的O(n^3)的算法：矩阵加法就是简单地将对应的位置的两个矩阵的元素相加：在ACM的题目中，我们一般考虑的是n阶方阵之间的乘法以及n阶方阵与n维向量（把向量看成n×1的矩阵）的乘法。矩阵乘法最重要的性质就是满足结合律，同时它另一个很重要的性质就是不满足交换率，这保证了矩阵的幂运算满足快速幂取模（A^k % MOD）算法：假设k = 27，则k的二进制表示为11011，所以按二进制展开，乘以相应的权值，可以看出：k的二进制的每一位矩阵A都要平方，在k二进制为1的位：末矩阵×平方后的A，在k二进制为0的位则末矩阵×E（单位矩阵），即不变。代码如下：重载按位与(乘方)和加法时注意，加法的优先级高于按位与*-+-^许多题目还要求S = A + A2 + A3 + … + Ak.。其实再作一次二分即可：只需计算log(n)个A的幂即可。 将二分若A中=m表示从i到j有m条有向边，则中=n表示从i经过k条有向边到达j，这样的走法有n种 矩阵在ACM里用处最大的就是加速常系数递推方程的计算，最经典的例子就是Fibonacci数列，如果普通的递推，计算第n项复杂度为o(n)，显然对于10^9左右的数据就力不从心了。如果用矩阵快速幂递推的话，计算第n项的复杂度为o(k3*log(n))，对应一般的题目已经绰绰有余了，有的题目可以根据矩阵的特殊性进行优化，可以达到o(k2*log(n))。 由常系数递推式右边有两项，所以向量和矩阵的规格都为2。容易如下递推： 实现计算Fibonacci数列第k项的代码如下：在朴素递推公式中采用线性递推，耗时，而采用矩阵快速幂时是将n二进制分解，耗时恰好可以将消去，最后有不能由去套矩阵凑，注意矩阵乘法不满足交换律