1.2 矩陣快速冪

1.2.1 矩陣快速冪的概念

矩陣A和矩陣B相乘的前提條件是矩陣A的列數和矩陣B的行數相等，相乘的結果矩陣的行數等于矩陣A的行數，列數等于矩陣B的列數；即，設A為m×p的矩陣，B為p×n的矩陣，則m×n的矩陣C為矩陣A與B的乘積，記作C=A×B，其中矩陣C中的第i行第j列元素。

所以，只有方陣（行數和列數相等）才能進行矩陣的冪運算。

根據線性代數的知識，n×n的方陣A和方陣B相乘，產生n×n的方陣C，方陣A、B和C分別用二維數組a、b和c表示，將二維數組c初始化為0，方陣相乘的程序段如下：

對于n×n的方陣A，給出正整數M，求方陣A的M次冪AM。結合快速冪算法和矩陣相乘算法，程序段如下，其中，函數mul(A,B)為方陣A和B相乘，res為當前的位權矩陣，初始時，res=A。

求Fibonacci數取模是矩陣快速冪的一個應用。Fibonacci數列遞推公式為：f(0)=0，f(1)=1，f(2)=1，f(n)=f(n-1)+f(n-2)，其中n≥3。則對于n≥3，Fibonacci數列遞推公式可以通過矩陣運算得到：。因此，求Fibonacci數列的第n項，可以通過對方陣通過矩陣快速冪求解n-2次獲得。

或者，對于n≥3，，而=，所以，，即，對方陣通過矩陣快速冪求解n次，產生方陣的第一行第二列的項或者第二行第一列的項，就是f(n)。

矩陣快速冪還可以求解形如f(n)=a×f(n-1)+b×f(n-2)+c的遞推式，其中a、b、c為常數，初始值f(1)和f(2)已知，則有。

矩陣快速冪也可以求解形如f(n)=cn-f(n-1)的遞推式，其中c為常數，初始值f(1)已知，則有。

【1.2.1.1 Fibonacci】

在Fibonacci整數序列中，F0=0，F1=1，且對n≥2，Fn=Fn-1+Fn-2。例如，Fibonacci序列的前十項為0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

Fibonacci序列的另一個公式是：

給出整數n，請計算Fn的最后4位。

輸入

輸入包含多個測試用例。每個測試用例一行，給出n(其中0≤n≤1000000000)。輸入用包含數字-1的一行結束。

輸出

對于每個測試用例，輸出Fn的最后4位。如果Fn的最后4位都是0，則輸出“0”；否則，忽略前導零（即，輸出Fn mod 10000）。

提示

本題和矩陣相乘關聯，兩個2×2方陣相乘：

任何2×2方陣的0次冪是單位矩陣：。

試題來源：Stanford Local 2006

在線測試：POJ 3070

試題解析

簡述題意：給出n，輸出Fn mod 10000的結果。

顯然，由Fibonacci序列公式可知，本題就是要求通過矩陣快速冪進行運算，矩陣的右上角的數字就是Fn。

參考程序

【1.2.1.2 Matrix Power Series】

給出一個n×n的方陣A和一個正整數k，請您計算S=A+A2+A3+…+Ak。

輸入

輸入只包含一個測試用例。輸入的第一行給出3個正整數n(n≤30)、k(k≤109)和m(m<104)。接下來的n行每行包含n個小于32768的非負整數，這是按行排列的矩陣A的元素。

輸出

以矩陣A的方式給出矩陣S，矩陣S中的元素除以m取余。

試題來源：POJ Monthly--2007.06.03

在線測試：POJ 3233

試題解析

本題采用矩陣快速冪和二分法求解。首先，可以通過矩陣快速冪求Ak；其次，可以對冪次k進行二分，每次將規模減半，分k為奇偶兩種情況：

●當k為偶數時，S(k)=(1+Ak/2)(A+A2+A3+…+Ak/2)=(1+Ak/2)×S(k/2)；

●當k為奇數時，S(k)=A+(A+A(k+1)/2)(A+A2+A3+…+Ak/2)=A+(A+A(k+1)/2)×S(k/2)。

例如，S(6)=A+A2+A3+…+A6=(1+A3)(A+A2+A3)=(1+A3)×S(3)，S(7)=A+A2+A3+…+A7=A+(A+A4)(A+A2+A3)=A+(A+A4)×S(3)。

參考程序

1.2.2 矩陣快速冪的應用

本節給出快速矩陣冪和其他算法相結合解題的實驗。題目1.2.2.1是將快速矩陣冪和加法原理相結合進行解題的實驗，題目1.2.2.2是將快速矩陣冪和調整的Floyd-Warshall算法相結合進行解題的實驗，而題目1.2.2.3則采用統計分析法，由局部解推導出矩陣的數學模型。

【1.2.2.1 Blocks】

Panda接到了一項任務，要給一排積木涂上顏色。Panda是一個聰明的孩子，他善于思考數學問題。假設一排積木有N塊，每塊積木可以涂成紅色、藍色、綠色或黃色。出于某些特殊的原因，Panda希望紅色的積木和綠色的積木數量都是偶數。在這種情況下，Panda想知道有多少種不同的方法來給這些積木涂上顏色。

輸入

輸入的第一行給出整數T(1≤T≤100)，表示測試用例的數目。接下來的T行每行給出一個整數N(1≤N≤109)，表示積木的數目。

輸出

對于每個測試用例，在一行輸出給積木涂上顏色的方法數。因為答案可能很大，所以答案要對10007取余。

試題來源：PKU Campus 2009 (POJ Monthly Contest-2009.05.17), Simon

在線測試：POJ 3734

試題解析

本題給出要涂上顏色的N塊積木，這N塊積木排成一排，每塊積木可以涂成紅色、藍色、綠色或黃色，問涂色結束后，紅色的積木和綠色的積木數量都是偶數的涂色方法有多少種（結果對10007取余）。

分析Panda涂色到第i塊積木時的情況。設Panda涂色到第i塊積木時，紅色的積木和綠色的積木數量都是偶數的方法數為ai，紅色的積木和綠色的積木數量一奇一偶的方法數為bi，紅色的積木和綠色的積木數量都是奇數的方法數為ci，則可以推導出如下公式：

●ai+1=2ai+bi，即：在紅色的積木和綠色的積木數量都是偶數的情況下，接下來的一塊積木不涂紅色或綠色，涂藍色或黃色，根據加法原理，方法數為2ai；在紅色的積木和綠色的積木數量一奇一偶的情況下，涂顏色數為奇數的積木，方法數為bi；而在紅色的積木和綠色的積木數量都是奇數的情況下，僅涂一塊積木，無法使紅色的積木和綠色的積木數量都是偶數。所以，根據加法原理，ai+1=2ai+bi。

●bi+1=2ai+2bi+2ci，即：在紅色的積木和綠色的積木數量都是偶數的情況下，接下來的一塊積木涂紅色或綠色，方法數為2ai；在紅色的積木和綠色的積木數量一奇一偶的情況下，接下來的一塊積木涂藍色或黃色，方法數為2bi；在紅色的積木和綠色的積木數量都是奇數的情況下，接下來的一塊積木涂紅色或綠色，方法數為2ci。根據加法原理，bi+1=2ai+2bi+2ci。

●ci+1=bi+2ci，即：在紅色的積木和綠色的積木數量都是偶數的情況下，僅涂一塊積木，無法使紅色的積木和綠色的積木數量都是奇數；在紅色的積木和綠色的積木數量一奇一偶的情況下，涂顏色數為偶數的積木，方法數為bi；在紅色的積木和綠色的積木數量都是奇數的情況下，接下來的一塊積木涂藍色或黃色，方法數為2ci。根據加法原理，ci+1=bi+2ci。

上述公式用矩陣表示如下：

所以，本題可以采用矩陣的快速冪運算求解。

參考程序

【1.2.2.2 Cow Relays】

N(2≤N≤1000000)頭奶牛決定在牧場使用T(2≤T≤100)條奶牛賽道進行接力賽，以進行它們的體能訓練計劃。

每條賽道連接著兩個不同的交點I1i(1≤I1i≤1000)和I2i(1≤I2i≤1000)，每個交點是至少兩條賽道的節點。奶牛們知道每條賽道的長度lengthi(1≤lengthi≤1000)、賽道連接的兩個交點，兩個交點直接連接著兩條不同的賽道的情況是不存在的。這些賽道構成一種數學上稱為圖的結構。

為了進行接力賽，N頭奶牛要站在不同的交點上，在有些交點上可能有多頭奶牛。奶牛要站在適當的位置，這樣就可以一頭奶牛接一頭奶牛地把接力棒傳遞下去，最后到達終點。

請編寫一個程序來確定奶牛所站的適當的位置，要找到連接起始交點（S）和結束交點（E）的最短路徑，并正好通過N條奶牛賽道。

輸入

第1行：由四個空格分隔的整數N、T、S和E。

第2～T+1行：第i+1行為用三個空格分隔的整數lengthi、I1i和I2i，描述第i條賽道。

輸出

輸出1行，給出一個整數，從交點S到交點E，且正好通過N條奶牛賽道的最短距離。

試題來源：USACO 2007 November Gold

在線測試：POJ 3613

試題解析

本題給出一個T條邊的帶權無向圖G，求從起點S到終點E恰好經過N條邊的最短路徑，其中，2≤T≤100，2≤N≤1000000。所以，從起點S到終點E恰好經過的路徑，邊可以重復。

對于圖的鄰接矩陣A，Ak[i][j]表示點i到點j恰好經過k條邊的路徑數。基于此，設帶權無向圖G表示為鄰接矩陣A，圖G的節點數為n，并設從節點i出發到節點j的長度為k的最短路徑為A(k)[i][j]，則有。對Floyd-Warshall算法進行調整如下：

這里要注意，Floyd-Warshall算法和調整的Floyd-Warshall算法有以下兩處不同。

●在Floyd-Warshall算法中，中間節點變量j1作為for三層循環的最外層的循環變量；而在調整的Floyd-Warshall算法中，中間節點變量j1作為for三層循環的最內層的循環變量。

●Floyd-Warshall算法用于計算圖中所有節點對之間的最短路徑；對鄰接矩陣A，一次調整的Floyd-Warshall算法運算，可以視為計算A2，求出的是每對節點間經過兩條邊的最短路徑，所以，要計算每對節點間經過N條邊的最短路徑，就要計算AN。

對于本題，因為N的數據范圍較大，所以AN的計算采用矩陣快速冪運算完成。此外，把INF設為0x3fffffff，即(1<<30)-1。

參考程序

【1.2.2.3 Training little cats】

Facer的寵物貓剛生下一窩小貓。考慮到這些可愛的貓的健康狀況，Facer決定讓這些貓做些運動。Facer為他的貓精心設計了一套動作。他現在要求你監督貓完成練習。Facer對貓設計的練習包含以下三種不同的動作。

●gi：給第i只貓一顆花生。

●ei：讓第i只貓吃掉它所擁有的花生。

●sij：讓第i只貓和第j只貓交換它們的花生。

所有的貓都要執行一個動作的序列，而且必須重復這個序列m次！可憐的貓！也只有Facer能想出這種餿主意。

請確定最終每只貓擁有的花生的數量，并輸出這些數量，以便保存這些值。

輸入

輸入由多個測試用例組成，以三個零（0 0 0）結束。對于每個測試用例，首先給出三個整數n、m和k，其中n是貓的數目，k是一個動作序列的長度。接下來的k行給出動作序列。其中m≤1000000000、n≤100、k≤100。

輸出

對于每個測試用例，在一行中輸出n個數字，表示最終每只貓擁有的花生的數量。

試題來源：PKU Campus 2009 (POJ Monthly Contest-2009.05.17), Facer

在線測試：POJ 3735

試題解析

本題給出n只貓，開始時每只貓有0顆花生，貓能做三種動作。給出一個由k個動作組成的動作序列，將一個動作序列做m次后，問：最終每只貓有多少顆花生？

對于本題，由于要重復一個動作序列m次，而m≤1000000000，因此不能采用模擬的方法解題。

本題采用矩陣表示動作。初始矩陣A為一個n+1元組，編號為0～n，0號元素固定為1，1～n號元素分別為對應的貓所擁有的花生數。以3只貓為例，初始矩陣A=(1 0 0 0)，再構造一個(n+1)×(n+1)的單位矩陣M，在單位矩陣M上表示動作。

gi：給第i只貓一顆花生，在M上使M[0][i]變為1。例如g 2，則：

，A×M=(1 0 1 0)，也就是第2只貓有一顆花生，其他貓沒有花生。

ei：讓第i只貓吃掉它所擁有的花生，在M上使M[i][i]變為0。例如，第1、第2、第3只貓分別有2、3、4顆花生，則當前矩陣A=(1 2 3 4)，當前動作為e 3，則：

，A×M=(1 2 3 0)，也就是第1、第2只貓分別有2顆和3顆花生，而第4只貓沒有花生。

sij：讓第i只貓和第j只貓交換它們的花生，在M上使第i列與第j互換。例如，第1、第2、第3只貓分別有2、3、4顆花生，則當前矩陣A=(1234)，當前動作為s 1 3，則

，A×M=(1 4 3 2)，也就是第1、第2、第3只貓分別有4、3、2顆花生，第1只貓和第3只貓交換了它們的花生。

對于k個動作，按動作順序，根據動作種類，對(n+1)×(n+1)的單位矩陣M處理如下。

●gi：給第i只貓一顆花生，M[0][i]++。

●ei：讓第i只貓吃掉它所擁有的花生，將M上第i列的所有元素置為0。

●sij：讓第i只貓和第j只貓交換它們的花生，在M上使第i列與第j互換。

這樣就得到了表示一個動作序列的矩陣T。由于要重復一個動作序列m次，因此最終每只貓擁有的花生的數量為A×Tm。

由于稀疏矩陣，在做矩陣乘法時要進行優化。

參考程序