【正文】 ^n = A^(n/2) * A^(n/2)；當(dāng)n為奇數(shù)時(shí)，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。經(jīng)典題目2 給定矩陣A，請(qǐng)快速計(jì)算出A^n（n個(gè)A相乘）的結(jié)果，輸出的每個(gè)數(shù)都mod p。假設(shè)初始時(shí)某個(gè)點(diǎn)的坐標(biāo)為x和y，下面5個(gè)矩陣可以分別對(duì)其進(jìn)行平移、旋轉(zhuǎn)、翻轉(zhuǎn)和旋轉(zhuǎn)操作。如果對(duì)每個(gè)點(diǎn)分別進(jìn)行模擬，那么m個(gè)操作總共耗時(shí)O(mn)。操作有平移、縮放、翻轉(zhuǎn)和旋轉(zhuǎn)這里的操作是對(duì)所有點(diǎn)同時(shí)進(jìn)行的。假設(shè)你有三個(gè)矩陣A、B、C，那么(AB)C和A(BC)的結(jié)果的第i行第j列上的數(shù)都等于所有A(ik)*B(kl)*C(lj)的和（枚舉所有的k和l）。為什么矩陣乘法不滿足交換律呢？廢話，交換過來后兩個(gè)矩陣有可能根本不能相乘。比如，下面的算式表示一個(gè)2行2列的矩陣乘以2行3列的矩陣，其結(jié)果是一個(gè)2行3列的矩陣。在數(shù)學(xué)中，一個(gè)矩陣說穿了就是一個(gè)二維數(shù)組。這里我們不介紹其它有關(guān)矩陣的知識(shí)，只介紹矩陣乘法和相關(guān)性質(zhì)。. . . .. .ACM中矩陣乘法的應(yīng)用（與原篇有刪改）by 三江小渡Categories: 數(shù)據(jù)結(jié)構(gòu)和算法, 算法理論、技巧、總結(jié)Tags: 矩陣乘法Comments: No CommentsPublished on: 2011 年 09 月 18 日矩陣乘法真的理解的不夠深！??！——————————————————–好像目前還沒有這方面題目的總結(jié)。這幾天連續(xù)看到四個(gè)問這類題目的人，今天在這里簡單寫一下。不要以為數(shù)學(xué)中的矩陣也是黑色屏幕上不斷變化的綠色字符。一個(gè)n行m列的矩陣可以乘以一個(gè)m行p列的矩陣，得到的結(jié)果是一個(gè)n行p列的矩陣，其中的第i行第j列位置上的數(shù)等于前一個(gè)矩陣第i行上的m個(gè)數(shù)與后一個(gè)矩陣第j列上的m個(gè)數(shù)對(duì)應(yīng)相乘后所有m個(gè)乘積的和。其中，結(jié)果的那個(gè)4等于2*2+0*1：下面的算式則是一個(gè)1 x 3的矩陣乘以3 x 2的矩陣，得到一個(gè)1 x 2的矩陣：矩陣乘法的兩個(gè)重要性質(zhì)：一，矩陣乘法不滿足交換律；二，矩陣乘法滿足結(jié)合律。為什么它又滿足結(jié)合律呢？仔細(xì)想想你會(huì)發(fā)現(xiàn)這也是廢話。經(jīng)典題目1 給定n個(gè)點(diǎn)，m個(gè)操作，構(gòu)造O(m+n)的算法輸出m個(gè)操作后各點(diǎn)的位置。其中翻轉(zhuǎn)是以坐標(biāo)軸為對(duì)稱軸進(jìn)行翻轉(zhuǎn)（兩種情況），旋轉(zhuǎn)則以原點(diǎn)為中心。利用矩陣乘法可以在O(m)的時(shí)間里把所有操作合并為一個(gè)矩陣，然后每個(gè)點(diǎn)與該矩陣相乘即可直接得出最終該點(diǎn)的位置，總共耗時(shí)O(m+n)。預(yù)先把所有m個(gè)操作所對(duì)應(yīng)的矩陣全部乘起來，再乘以(x,y,1)，即可一步得出最終點(diǎn)的位置。由于矩陣乘法具有結(jié)合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。這就告訴我們，計(jì)算A^n也可以使用二分快速求冪的方法。根據(jù)這里的一些結(jié)果，我們可以在計(jì)算過程中不斷取模，避免高精度運(yùn)算。輸出的數(shù)據(jù)mod m。這道題兩次二分，相當(dāng)經(jīng)典。然后我們需要對(duì)整個(gè)題目的數(shù)據(jù)規(guī)模k進(jìn)行二分。我們二分求出A^3后再遞歸地計(jì)算A + A^2 + A^3，即可得到原問題的答案。（有木有感覺很強(qiáng)大？