矩阵乘法(完整版)实用资料.doc

《矩阵乘法(完整版)实用资料.doc》由会员分享，可在线阅读，更多相关《矩阵乘法(完整版)实用资料.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、矩阵乘法（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载）fibonacci斐波那契数列(矩阵复习）2021-11-02 21:03描述 Description著名的斐波那契数列fn=1 n=1,2 fn-1+fn-2 n2现在求第n项，由于fn可能很大，你只需要输出mod 32768的值即可。输入格式 Input Format仅有一行，为n,1=n0 do begin if odd(n) then begin fillchar(c,sizeof(c),0); for k:=1 to 2 do for i:=1 to 1 do for j:=1 to 2 do ci,j:=(

2、ci,j+ai,k*bk,j) and 32767; a:=c; end; fillchar(cc,sizeof(cc),0); for k:=1 to 2 do for i:=1 to 2 do for j:=1 to 2 do cci,j:=(cci,j+bi,k*bk,j) and 32767; b:=cc; n:=n shr 1; end;writeln(a1,2);end.矩阵乘法百科名片矩阵乘法是一种高效的算法可以把一些一维递推优化到log（ n )，还可以求路径方案等，所以更是是一种应用性极强的算法。矩阵，是线性代数中的基本概念之一。一个mn的矩阵就是mn个数排成m行n列的一个数

3、阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。矩阵乘法看起来很奇怪，但实际上非常有用，应用也十分广泛。目录基本定义它是这样定义的，只有当矩阵A的列数与矩阵B的行数相等时AB才有意义。一个mn的矩阵a（m,n)左乘一个np的矩阵b（n,p)，会得到一个mp的矩阵c（m,p)，满足 矩阵乘法满足结合率，但不满足交换率 一般的矩乘要结合快速幂才有效果 一般矩乘的代码：function mul( a , b : Tmatrix ) : Tmatrix; var i,j,k : longint; c : Tmatrix; begin fillchar( c , size

4、of( c ) , 0 ); for k:=0 to n do for i:=0 to m do for j:=0 to p do begin inc( c i , j , a i , k *b k , j ); if c i , j ra then c i , j :=c i , j mod ra; end; mul:=c; end; 编辑本段经典题目好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人，今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。 不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组

5、。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1： 下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵： 矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢？废话，交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢？仔细想想你会发现这也是废

6、话。假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。 经典题目1给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转 这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵

7、可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。 经典题目2给定矩阵A，请快速计算出An（n个A相乘）的结果，输出的每个数都mod p。 由于矩阵乘法具有结合律，因此A4 = A * A * A * A = (A*A) * (A*A) = A2 * A2。我们可以得到这样的结论：当n为偶数时，An = A(n/2) * A(n/2)；当n为奇数时，An = A(n/2) * A(n/2) * A （其中n/2取整）。这就告诉我们，计算An也可以使用二分快速求幂的方法。例如，为了算出A25的值，我们只需要递归地

8、计算出A12、A6、A3的值即可。根据这里的一些结果，我们可以在计算过程中不断取模，避免高精度运算。 经典题目3POJ3233 (感谢rmq) 题目大意：给定矩阵A，求A + A2 + A3 + . + Ak的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k=109。 这道题两次二分，相当经典。首先我们知道，Ai可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如，当k=6时，有： A + A2 + A3 + A4 + A5 + A6 =(A + A2 + A3) + A3*(A + A2 + A3) 应用这个式子后，规模k减小了一半。我们二分求出A3后再递归地计算

9、A + A2 + A3，即可得到原问题的答案。 经典题目4VOJ1049 题目大意：顺次给出m个置换，反复使用这m个置换对初始序列进行操作，问k次置换后的序列。m=10, kj。令C=A*A，那么C(i,j)=A(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出Ak即可。 经典题目9用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M=5，N011-111、111-110-111和111-000-111，这与用多米诺骨牌覆盖3x2矩形

10、的方案一一对应。这样这个题目就转化为了我们前面的例题8。 后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。 经典题目10POJ2778 题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n=2 000 000 000。 下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C

11、结尾和以?结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到?有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到?有2种方案（后面加G或C），从GG到?有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串

12、匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从?状态到所有其它状态的路径数总和。 题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是1003 * log(n)，AC了。 最后给出第9题的代码供大家参考（今天写的，熟悉了一下C+的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说： Matrix67原创，转贴请注明出处。 #include #define SIZE (1m) #define MAX_SIZE 32 using namespace std; class CMatrix pu

13、blic: long elementMAX_SIZEMAX_SIZE; void setSize(int); void setModulo(int); CMatrix operator* (CMatrix); CMatrix power(int); private: int size; long modulo; ; void CMatrix:setSize(int a) for (int i=0; ia; i+) for (int j=0; ja; j+) elementij=0; size = a; void CMatrix:setModulo(int a) modulo = a; CMat

14、rix CMatrix:operator* (CMatrix param) CMatrix product; product.setSize(size); product.setModulo(modulo); for (int i=0; isize; i+) for (int j=0; jsize; j+) for (int k=0; ksize; k+) product.elementij+=elementik*param.elementkj; product.elementij%=modulo; return product; CMatrix CMatrix:power(int exp)

15、CMatrix tmp = (*this) * (*this); if (exp=1) return *this; else if (exp & 1) return tmp.power(exp/2) * (*this); else return tmp.power(exp/2); int main() const int validSet=0,3,6,12,15,24,27,30; long n, m, p; CMatrix unit; scanf(%d%d%d, &n, &m, &p); unit.setSize(SIZE); for(int i=0; iSIZE; i+) for(int

16、j=0; jSIZE; j+) if( (i)&j) = (i)&(SIZE-1) ) bool isValid=false; for (int k=0; k8; k+)isValid=isValid|(i&j)=validSetk; unit.elementij=isValid; unit.setModulo(p); printf(%d, unit.power(n).elementSIZE-1SIZE-1 ); return 0; 理解矩阵乘法大多数人在高中，或者大学低年级，都上过一门课线性代数。这门课其实是教矩阵。刚学的时候，还蛮简单的，矩阵加法就是相同位置的数字加一下。矩阵减法也类似。矩

17、阵乘以一个常数，就是所有位置都乘以这个数。但是，等到矩阵乘以矩阵的时候，一切就不一样了。这个结果是怎么算出来的？教科书告诉你，计算规则是，第一个矩阵第一行的每个数字（2 和1），各自乘以第二个矩阵第一列对应位置的数字（1 和1），然后将乘积相加（ 2 x 1 + 1 x 1），得到结果矩阵左上角的那个值3。也就是说，结果矩阵第m行与第n列交叉位置的那个值，等于第一个矩阵第m行与第二个矩阵第n列，对应位置的每个值的乘积之和。怎么会有这么奇怪的规则？我一直没理解这个规则的含义，导致线性代数这门课就没学懂。研究生时发现，线性代数是向量计算的基础，很多重要的数学模型都要用到向量计算，所以我做不了复杂模

18、型。这一直让我有点伤心。前些日子，受到一篇文章的启发，我终于想通了，矩阵乘法到底是什么东西。关键就是一句话，矩阵的本质就是线性方程式，两者是一一对应关系。如果从线性方程式的角度，理解矩阵乘法就毫无难度。下面是一组线性方程式。矩阵的最初目的，只是为线性方程组提供一个简写形式。老实说，从上面这种写法，已经能看出矩阵乘法的规则了：系数矩阵第一行的 2 和1，各自与x 和 y 的乘积之和，等于3。不过，这不算严格的证明，只是线性方程式转为矩阵的书写规则。下面才是严格的证明。有三组未知数 x、y 和 t，其中 x 和 y 的关系如下。x 和 t的关系如下。有了这两组方程式，就可以求 y 和 t 的关系。

19、从矩阵来看，很显然，只要把第二个矩阵代入第一个矩阵即可。从方程式来看，也可以把第二个方程组代入第一个方程组。上面的方程组可以整理成下面的形式。最后那个矩阵等式，与前面的矩阵等式一对照，就会得到下面的关系。矩阵乘法的计算规则，从而得到证明。阅读材料：两个具体矩阵合成的乘法公式的验证通过前面的学习，我们知道两个变换A和B的合成是一个新的变换，比如：两个旋转变换矩阵A= 0-10-11 B=和都将向量 10 2逆时针旋转90度，那么很自然10的想法就是它们的合成变换A B将向量逆时针旋转180度，而将向量逆时针旋转180度的变换我们可以用矩阵 -10来表示（为什么？）。于是，我们思考对于一般的两个0

20、-1矩阵变换A和B，它们的合成变换A B是否能用一个新的矩阵表示出来，接下来我们就用具体的几个例子来验证：两个一般矩阵变换合成的乘法公式。即对于任意两个矩阵变换abuv A= 和B= ，则它们的合成是一个新变换C，记C=A B， 且满足 stcdabuvau+bsav+btC= cd st= cu+dscv+dt（*） 范例1：两次旋转cos我们取矩阵A= sin-sincos，B= sincos-sin ，它们分别表示把平面上cos的任意向量逆时针旋转度和逆时针旋转度的变换。利用A和B，对平面上的任意向量连续做两次变换，即先逆时针旋转度，再逆时针旋转度。实际上连续完成这两个变换，变换的效果可

21、以用一个变换来表示，即使向量逆时针旋转+度的变换，矩阵+)-sin(+)cos(C= 恰好表示了这一变换。让我们来看下面的几何解释：（其 sin(+)cos(+)中向量就是向量OD）旋转+度到D点。它们的合成是逆时针旋转+度的旋转变换下面我们再从代数上验证，通过前面的学习我们知道所谓两个矩阵变换相等就是指它们作用在任意平面向量上的结果一样，并且为了验证的简便，根据矩阵的线性性质，我们只需要验证它们在单位向量 再用等式 y=x 0+y 1即可说明任意向 0和 1上的作用，量的正确性。 10x10cos11 B A =B(A)=B 0 0 sin-sin1cos =B cos0sincos= si

22、n-sincoscos(+) = sin sin(+) cos+)-sin(+)1cos(+)1cos(11 C =B A=C，于是 0 sin(+)cos( ， +)0sin(+)0000 B A =B(A 1 1)=cosBsin-sin0 1=cos-sinB cos cos= sin01-sin-sin-sin(+) = coscoscos(+) C = +)-sin(+)0-sin(+)cos(00 =B A=C，于是 +)1cos(+)sin(+)cos(11于是B A=C，得证。范例2：两次压缩 0101，B= 1 （m,n1），它们分别表示把平面上的任意 0mn11向量向x方向

23、垂直压缩为和的变换。利用A和B，对平面上的任意向量连续做两次mn1我们取矩阵A= 011，再向x方向垂直压缩为。实际上连续完成这两个变mn1换，变换的效果可以用一个变换来表示，即使向量向x方向垂直压缩为的变换，矩mn101恰好表示了这一变换。让我们来看下面的几何解释：阵C= （其中向量就是向 0mn量OD）变换，即先向x方向垂直压缩为y矩阵变换A下面我们再从代数上验证，通过前面的学习我们知道所谓两个矩阵变换相等就是指它们作用在任意平面向量上的结果一样，并且为了验证的简便，根据矩阵的线性性质，我们只需要验证它们在单位向量 再用等式 y=x 0+y 1即可说明任意向 0和 1上的作用，量的正确性。

24、10x10111 B A 0=B(A 0)=B 00111 1 =B 0= 0 0m0111 = 0 0n11 C 0= 0011111 B A=C，于是， = 0000mn00010001 =B 1= 1 1= 1 1 1 mmnmmn100 B A 1=B(A 1)=B 01000000 = 1，于是B A1 =C C = 1 1 1 0 1 mnm于是B A=C，得证。范例3：先切变，再反射1a10 我们取矩阵A= ，B= ，它们分别表示把平面上的任意向量作切010-1变变换和关于x轴对称的变换。利用A和B，对平面上的任意向量连续做两次变换，即先作切变变换，再关于x轴对称。实际上连续完成

25、这两个变换，变换的效果可以用一个变换来表示，矩阵C= 01a恰好表示了这一变换。让我们来看下面的几何解释：（其中向量-1就是向量OD）下面我们再从代数上验证，通过前面的学习我们知道所谓两个矩阵变换相等就是指它们作用在任意平面向量上的结果一样，并且为了验证的简便，根据矩阵的线性性质，我们只需10x要验证它们在单位向量 再用等式 y= 0和 1上的作用，量的正确性。 1x 0+0y 1即可说明任意向1a11111011 B A =B(A)=B=B 0 0 0= 0-1 0= 0 01 011a1111 C = = ，于是B A =C ， 00-100001a000a10aa B A =B(A)=B=B 1 1 1= 0-1 1= -1 01 101a0a00 C 1= 0-1 1= -1，于是B A 1=C 1 于是B A=C，得证。请同学们按照上述证明的办法求下面矩阵变换的合成变换矩阵，并用矩阵的乘法公式验证：0-1-10 1、A= ，B= 100-11100 1 2、A=2，B= 00133、A=1a1bB=，