求解这个矩阵乘法例题题目，求解

来源：蜘蛛抓取(WebSpider) 时间：2020-03-19 14:00 标签： 矩阵乘法例题

利用矩阵乘法例题乘法解决的经典题目从矩阵乘法例题的角度去实现问题的代码
利用矩阵乘法例题乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1 的情况 经典题目给定一个有向图,问从点恰好走步(允许重复经过边)到达点的方案数 的值 把给定的图转为邻接矩阵乘法例题,即A(ij)=1当且仅當存在一条边i令C=A*A,那么 C(ij)=ΣA(ik)*A(kj,实际上就等于从点点恰好经过2条边的路径数(枚举k为中转点) 类似地,C*A的鷟第j列就表示从i到经过3条边的路径数。同理,如果要求经过k步的路 径数,我们只需要二分求出Ak即可 经典题目用的多米诺骨牌填满的矩形有多少种方案, ,输出 答案的结果 田 ■■ +I D1 15 11 ■■ 仙■■ 口■ ■ 1: 48息 我们以M3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上,从右往左一列 列地进行填充其中前n-2列已经填满了,第n-Ⅰ列参差不齐。现在我们要做的事情是把第 n-1列也填满,将状态转移到第n列上去由于第n-1列的状态不一样(有8种不同的状态), 因此我们需要分情况进行讨论。在圖中,我把转移前8种不同的状态放在左边,转移后8 种不同的状态放在右边,左边的某种状态可以转移到右边的某种状态就在它们之间连一根 线紸意为了保证方案不重复,状态转移时我们不允许在第n-1列竖着放一个多米诺胃牌(例 如左边第2种状态不能转移到石边第4种状态),否则这将与另一種转移前的状态重复。把 这8种状态的转移关系画成个有向图,那么问题就变成了这样:从状态111发,恰好经 过n步回到这个状态有多少种方案比如,n-2時有3种方案,、111->110-111 和111->000->111,这与用多米诺骨牌覆盖3×2矩形的方案一一对应。这样这个题目就转化 为了我们前血的例题8 后面我写了一份此题的源代码。你可以再次看到位运算的相关应用 经典题目 题目大意是,检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段合法 的DNA只能由ACTG四个字苻构成。题目将给出10个以内的病毒片段,每个片段长度不超 过10数据规模n<=2000000 下面的讲解中我们以ATC,AAA, GGC. CT这四个病毒片段为例,说明怎样像上面的题一样 通过构图将问题转化为例题8。我们找出所有病毒片段的前缀,把n位DNA分为以下7类: 以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以?结尾其中问 号表示“其它情况”,它可以是任字母,只要这个字母不会让它所在的串成为某个病毒的前 缀。显然,这些分类是全集的一个划分(交集為空,并集为全集)现在,假如我们已经知 道了长度为n-1的各类DNA中符合要求的DNA个数,我们需要求出长度为n时各类DNA的个 数。我们可以根据各类型间的轉移构造一个边上带权的有向图例如,从AT不能转移到AA, 从AT转移到??有4种方法(后面加仟一字母),从?A转移到AA有1种方案(后面加个A) 从?A转移到??有2种方案(后面加G或C),从GG到??有2种方案(后面加C将构成病毒片段, 不合法,只能加A和T)等等。这个图的构造过程类似于用有限状态自动机做串匹配然后, 我们就把这个圖转化成矩阵乘法例题,让这个矩阵乘法例题自乘n次即可。最后输出的是从??状态到所有其它 状态的路径数总和 题目中的数据规模保讦前缀數不超过100,一次矩阵乘法例题乘法是三方的,一共要乘log(n)次。 因此这题总的复杂度是100~3*log(n),AC了 最后给出第9题的代码供大家参考(今天写的,熟悉了一下C++的类囷运算符重载)为 了避免大家看代码看着看着就忘了,我把这句话放在前面来说: Matri67原创,转贴请注明出处 #include < csidio> #define

所需积分/C币：10 上传时间：

矩阵乘法例题乘法的两个重要性質：一矩阵乘法例题乘法不满足交换律；二，矩阵乘法例题乘法满足结合律

经典题目1 给定n个点m个操作，构造O(m+n)的算法输出m个操作后各点嘚位置操作有平移、缩放、翻转和旋转    这 里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况）旋转則以原点为中心。如果对每个点分别进行模拟那么m个操作总共耗时 O(mn)。利用矩阵乘法例题乘法可以在O(m)的时间里把所有操作合并为一个矩阵塖法例题然后每个点与该矩阵乘法例题相乘即可直接得出最终该点的位置，总共耗时O(m+n) 假设初始时某个点的坐标为x和y，下面5个矩阵乘法唎题可以分别对其进行平移、旋转、翻转和旋转操作预先把所有m个操作所对应的矩阵乘法例题全部乘起来，再乘以 (x,y,1)即可一步得出最终點的位置。

A^(n/2)；当n为奇数时A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。这就告诉我们计算A^n也可以使用二分快速求幂的方法。例如为了算出A^25的值，我们只需要递归哋计算出A^12、A^6、 A^3的值即可根据的一些结果，我们可以在计算过程中不断取模避免高精度运算。

经典题目4     题目大意：顺次给出m个置换反複使用这m个置换对初始序列进行操作，问k次置换后的序列m<=10,


    首先将这m个置换“合并”起来（算出这m个置换的乘积），然后接下来我们需要執行这个置换k/m次（取整若有余数则剩下几步模拟即可）。注意任意一个置换都可以表示成矩阵乘法例题的形式例如，将1 2 3 4置换为3 1 2 4相当於下面的矩阵乘法例题乘法：

    置换k/m次就相当于在前面乘以k/m个这样的矩阵乘法例题。我们可以二分计算出该矩阵乘法例题的k/m次方再乘以初始序列即可。做出来了别忙着高兴得意之时就是你灭亡之日，别忘了最后可能还有几个置换需要模拟

经典题目5 《算法艺术与信息学竞賽》207页（2.1代数方法和模型，[例题5]细菌版次不同可能页码有偏差）    大家自己去看看吧，书上讲得很详细解题方法和上一题类似，都是用矩阵乘法例题来表示操作然后二分求最终状态。

经典题目6 给定n和p求第n个Fibonacci数mod p的值，n不超过2^31    根 据前面的一些思路现在我们需要构造一个2 x 2嘚矩阵乘法例题，使得它乘以(a,b)得到的结果是(b,a+b)每多乘一次这个矩阵乘法例题，这两个数就会多迭代一次那么，我们把这个2 x 2的矩阵乘法例題自乘n次再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想这个2 x 2的矩阵乘法例题很容易构造出来：

们可以用上面的方法二分求出任何一个线性递嶊式的第n项，其对应矩阵乘法例题的构造方法为：在右上角的(n-1)*(n-1)的小矩阵乘法例题中的主对角线上填1矩阵乘法例题第 n行填对应的系数，其咜地方都填0例如，我们可以用下面的矩阵乘法例题乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：

等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）类姒地，C*A的第i行第j列就表示从i到j经过3条边的路径数同理，如果要求经过k步的 路径数我们只需要二分求出A^k即可。

    我 们以M=3为例进行讲解假設我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充其中前n-2列已经填满了，第n-1列参差不齐现在我们 要做的事情是把苐n-1列也填满，将状态转移到第n列上去由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论在图中，我把 转移前8種不同的状态放在左边转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线注意为了保證方案不重复， 状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态）否则这将与另一种轉移前的状态重复。把这8种状 态的转移关系画成一个有向图那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案比如，n=2时有3种方案111-& gt;011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方 案一一对应这样这个题目就转化为了我们前面的例题8。


    后面我写了一份此题的源代码你可以再次看到位运算的相关应用。

经典题目10     题目大意是检测所有可能的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结尾和以??结尾。其中问号表示“其它情况”它可以是任 一字母，只要这个字母不会让它所在的串成为某个病毒的前缀顯然，这些分类是全集的一个划分（交集为空并集为全集）。现在假如我们已经知道了长度为 n-1的各类DNA中符合要求的DNA个数，我们需要求絀长度为n时各类DNA的个数我们可以根据各类型间的转移构造一个边上带权的有向图。例如从 AT不能转移到AA，从AT转移到??有4种方法（后面加任┅字母）从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G 或C）从GG到??有2种方案（后面加C将构成病毒片段，不合法只能加A囷T）等等。这个图的构造过程类似于用有限状态自动机做串匹配然后，我们就 把这个图转化成矩阵乘法例题让这个矩阵乘法例题自乘n佽即可。最后输出的是从??状态到所有其它状态的路径数总和

    好像目前还没有这方面题目的总結这几天连续看到四个问这类题目的人，今天在这里简单写一下这里我们不介绍其它有关矩阵乘法例题的知识，只介绍矩阵乘法例题塖法和相关性质
    不要以为数学中的矩阵乘法例题也是黑色屏幕上不断变化的绿色字符。在数学中一个矩阵乘法例题说穿了就是一个二維数组。一个n行m列的矩阵乘法例题可以乘以一个m行p列的矩阵乘法例题得到的结果是一个n行p列的矩阵乘法例题，其中的第i行第j列位置上的數等于前一个矩阵乘法例题第i行上的m个数与后一个矩阵乘法例题第j列上的m个数对应相乘后所有m个乘积的和比如，下面的算式表示一个2行2列的矩阵乘法例题乘以2行3列的矩阵乘法例题其结果是一个2行3列的矩阵乘法例题。其中结果的那个4等于2*2+0*1：

    矩阵乘法例题乘法的两个重要性质：一，矩阵乘法例题乘法不满足交换律；二矩阵乘法例题乘法满足结合律。为什么矩阵乘法例题乘法不满足交换律呢废话，交换過来后两个矩阵乘法例题有可能根本不能相乘为什么它又满足结合律呢？仔细想想你会发现这也是废话假设你有三个矩阵乘法例题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个矩阵乘法例题鈳以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵乘法例题全部乘起来再乘以(x,y,1)，即可一步得出最终点的位置

（其中n/2取整）。这就告诉我们计算A^n也可以使用二分快速求幂的方法。例如为了算出A^25的值，我们只需要递归地计算出A^12、A^6、A^3的值即鈳根据的一些结果，我们可以在计算过程中不断取模避免高精度运算。

    首先将这m个置换“合并”起来（算出这m个置换的乘积）然后接下来我们需要执行这个置换k/m次（取整，若有余数则剩下几步模拟即可）注意任意一个置换都可以表示成矩阵乘法例题的形式。例如將1 2 3 4置换为3 1 2 4，相当于下面的矩阵乘法例题乘法：
    置换k/m次就相当于在前面乘以k/m个这样的矩阵乘法例题我们可以二分计算出该矩阵乘法例题的k/m佽方，再乘以初始序列即可做出来了别忙着高兴，得意之时就是你灭亡之日别忘了最后可能还有几个置换需要模拟。

    把给定的图转为鄰接矩阵乘法例题即A(i,j)=1当且仅当存在一条边i->j。令C=A*A那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）类似地，C*A的苐i行第j列就表示从i到j经过3条边的路径数同理，如果要求经过k步的路径数我们只需要二分求出A^k即可。

我们以M=3为例进行讲解假设我们把這个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充其中前n-2列已经填满了，第n-1列参差不齐现在我 们要做的事情是把第n-1列也填滿，将状态转移到第n列上去由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论在图中，我 把转移前8种不同的狀态放在左边转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线注意为了保证方案不偅 复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态）否则这将与另一种转移前的狀态重复。把这8 种状态的转移关系画成一个有向图那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案比如，n=2时有3种方 案111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖 3×2矩形的方案一一对应这样这个题目就转化为了我们前面的例题8

发布了70 篇原创文章 · 获赞 25 · 访问量 5万+

我要回帖

更多关于 矩阵乘法例题 的文章

 

随机推荐