1、 好像目前還沒有這方面題目的總結。這幾天連續看到四個問這類題目的人，今天在這里簡單寫一下。這里我們不介紹其它有關矩陣的知識，只介紹矩陣乘法和相關性質。 不要以為數學中的矩陣也是黑色屏幕上不斷變化的綠色字符。在數學中，一個矩陣說穿了就是一個二維數組。一個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的矩陣

2、乘以3 x 2的矩陣，得到一個1 x 2的矩陣： 矩陣乘法的兩個重要性質：一，矩陣乘法不滿足交換律；二，矩陣乘法滿足結合律。為什么矩陣乘法不滿足交換律呢？廢話，交換過來后兩個矩陣有可能根本不能相乘。為什么它又滿足結合律呢？仔細想想你會發現這也是廢話。假設你有三個矩陣A、B、C，那么(AB)C和A(BC)的結果的第i行第j列上的數都等于所有A(ik)*B(kl)*C(lj)的和（枚舉所有的k和l）。經典題目1 給定n個點，m個操作，構造O(m+n)的算法輸出m個操作后各點的位置。操作有平移、縮放、翻轉和旋轉 這里的操作是對所有點同時進行的。其中翻轉是以坐標軸為對稱軸進行翻轉（兩種情況），旋轉則以

3、原點為中心。如果對每個點分別進行模擬，那么m個操作總共耗時O(mn)。利用矩陣乘法可以在O(m)的時間里把所有操作合并為一個矩陣，然后每個點與該矩陣相乘即可直接得出最終該點的位置，總共耗時O(m+n)。假設初始時某個點的坐標為x和y，下面5個矩陣可以分別對其進行平移、旋轉、翻轉和旋轉操作。預先把所有m個操作所對應的矩陣全部乘起來，再乘以(x,y,1)，即可一步得出最終點的位置。 經典題目2 給定矩陣A，請快速計算出An（n個A相乘）的結果，輸出的每個數都mod p。 由于矩陣乘法具有結合律，因此A4 = A * A * A * A = (A*A) * (A*A) = A2 * A2。我們可以得

4、到這樣的結論：當n為偶數時，An = A(n/2) * A(n/2)；當n為奇數時，An = A(n/2) * A(n/2) * A （其中n/2取整）。這就告訴我們，計算An也可以使用二分快速求冪的方法。例如，為了算出A25的值，我們只需要遞歸地計算出A12、A6、A3的值即可。根據這里的一些結果，我們可以在計算過程中不斷取模，避免高精度運算。經典題目3 POJ3233 (感謝rmq) 題目大意：給定矩陣A，求A + A2 + A3 + . + Ak的結果（兩個矩陣相加就是對應位置分別相加）。輸出的數據mod m。k<=109。 這道題兩次二分，相當經典。首先我們知道，Ai可以二分求出

5、。然后我們需要對整個題目的數據規模k進行二分。比如，當k=6時，有： A + A2 + A3 + A4 + A5 + A6 =(A + A2 + A3) + A3*(A + A2 + A3) 應用這個式子后，規模k減小了一半。我們二分求出A3后再遞歸地計算A + A2 + A3，即可得到原問題的答案。經典題目4 VOJ1049 題目大意：順次給出m個置換，反復使用這m個置換對初始序列進行操作，問k次置換后的序列。m<=10, k<231。 首先將這m個置換“合并”起來（算出這m個置換的乘積），然后接下來我們需要執行這個置換k/m次（取整，若有余數則剩下幾步模擬即可）。注意任意一個置

6、換都可以表示成矩陣的形式。例如，將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不超過231 根據前面的一些思路，現在我們需要構

7、造一個2 x 2的矩陣，使得它乘以(a,b)得到的結果是(b,a+b)。每多乘一次這個矩陣，這兩個數就會多迭代一次。那么，我們把這個2 x 2的矩陣自乘n次，再乘以(0,1)就可以得到第n個Fibonacci數了。不用多想，這個2 x 2的矩陣很容易構造出來： 經典題目7 VOJ1067 我們可以用上面的方法二分求出任何一個線性遞推式的第n項，其對應矩陣的構造方法為：在右上角的(n-1)*(n-1)的小矩陣中的主對角線上填1，矩陣第n行填對應的系數，其它地方都填0。例如，我們可以用下面的矩陣乘法來二分計算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k項： 利用矩陣乘

8、法求解線性遞推關系的題目我能編出一卡車來。這里給出的例題是系數全為1的情況。經典題目8 給定一個有向圖，問從A點恰好走k步（允許重復經過邊）到達B點的方案數mod p的值 把給定的圖轉為鄰接矩陣，即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步的路徑數，我們只需要二分求出Ak即可。經典題目9 用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M<=5，N<231，

9、輸出答案mod p的結果 我們以M=3為例進行講解。假設我們把這個矩形橫著放在電腦屏幕上，從右往左一列一列地進行填充。其中前n-2列已經填滿了，第n-1列參差不齊。現在我們要做的事情是把第n-1列也填滿，將狀態轉移到第n列上去。由于第n-1列的狀態不一樣（有8種不同的狀態），因此我們需要分情況進行討論。在圖中，我把轉移前8種不同的狀態放在左邊，轉移后8種不同的狀態放在右邊，左邊的某種狀態可以轉移到右邊的某種狀態就在它們之間連一根線。注意為了保證方案不重復，狀態轉移時我們不允許在第n-1列豎著放一個多米諾骨牌（例如左邊第2種狀態不能轉移到右邊第4種狀態），否則這將與另一種轉移前的狀態重復。把這8

10、種狀態的轉移關系畫成一個有向圖，那么問題就變成了這樣：從狀態111出發，恰好經過n步回到這個狀態有多少種方案。比如，n=2時有3種方案，111->011->111、111->110->111和111->000->111，這與用多米諾骨牌覆蓋3x2矩形的方案一一對應。這樣這個題目就轉化為了我們前面的例題8。 后面我寫了一份此題的源代碼。你可以再次看到位運算的相關應用。經典題目10 POJ2778 題目大意是，檢測所有可能的n位DNA串有多少個DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四個字符構成。題目將給出10個以內的病毒片段，每個片段長度不超

11、過10。數據規模n<=2 000 000 000。 下面的講解中我們以ATC,AAA,GGC,CT這四個病毒片段為例，說明怎樣像上面的題一樣通過構圖將問題轉化為例題8。我們找出所有病毒片段的前綴，把n位DNA分為以下7類：以AT結尾、以AA結尾、以GG結尾、以?A結尾、以?G結尾、以?C結尾和以?結尾。其中問號表示“其它情況”，它可以是任一字母，只要這個字母不會讓它所在的串成為某個病毒的前綴。顯然，這些分類是全集的一個劃分（交集為空，并集為全集）?，F在，假如我們已經知道了長度為n-1的各類DNA中符合要求的DNA個數，我們需要求出長度為n時各類DNA的個數。我們可以根據各類型間的轉移構造

12、一個邊上帶權的有向圖。例如，從AT不能轉移到AA，從AT轉移到?有4種方法（后面加任一字母），從?A轉移到AA有1種方案（后面加個A），從?A轉移到?有2種方案（后面加G或C），從GG到?有2種方案（后面加C將構成病毒片段，不合法，只能加A和T）等等。這個圖的構造過程類似于用有限狀態自動機做串匹配。然后，我們就把這個圖轉化成矩陣，讓這個矩陣自乘n次即可。最后輸出的是從?狀態到所有其它狀態的路徑數總和。 題目中的數據規模保證前綴數不超過100，一次矩陣乘法是三方的，一共要乘log(n)次。因此這題總的復雜度是1003 * log(n)，AC了。 最后給出第9題的代碼供大家參考（今天寫的，熟悉了一

13、下C+的類和運算符重載）。為了避免大家看代碼看著看著就忘了，我把這句話放在前面來說： Matrix67原創，轉貼請注明出處。#include <cstdio>#define SIZE (1<<m)#define MAX_SIZE 32using namespace std;class CMatrix public: long elementMAX_SIZEMAX_SIZE; void setSize(int); void setModulo(int); CMatrix operator* (CMatrix); CMatrix power(int); private: i

14、nt size; long modulo;void CMatrix:setSize(int a) for (int i=0; i<a; i+) for (int j=0; j<a; j+) elementij=0; size = a;void CMatrix:setModulo(int a) modulo = a;CMatrix CMatrix:operator* (CMatrix param) CMatrix product; product.setSize(size); product.setModulo(modulo); for (int i=0; i<size; i+

15、) for (int j=0; j<size; j+) for (int k=0; k<size; k+) product.elementij+=elementik*param.elementkj; product.elementij%=modulo; return product;CMatrix CMatrix:power(int exp) 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; i<SIZE; i+) for(int j=0; j<SIZE; j+) i