十個利用矩陣乘法解決的經典題目

日期：2019年5月26日

正文共：2558字7圖

預計閱讀時間：7分鐘

來源：Matrix67

好像目前還沒有這方面題目的總結。這幾天連續看到四個問這類題目的人，今天在這裡簡單寫一下。這裡我們不介紹其它有關矩陣的知識，只介紹矩陣乘法和相關性質。

不要以為數學中的矩陣也是黑色屏幕上不斷變化的綠色字符。在數學中，一個矩陣說穿了就是一個二維數組。一個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的矩陣：

 

矩陣乘法的兩個重要性質：一，矩陣乘法不滿足交換律；二，矩陣乘法滿足結合律。為什麼矩陣乘法不滿足交換律呢？廢話，交換過來後兩個矩陣有可能根本不能相乘。為什麼它又滿足結合律呢？仔細想想你會發現這也是廢話。假設你有三個矩陣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)，即可一步得出最終點的位置。

經典題目2 

給定矩陣A，請快速計算出A^n（n個A相乘）的結果，輸出的每個數都mod p。

由於矩陣乘法具有結合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我們可以得到這樣的結論：當n為偶數時，A^n = A^(n/2) * 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的值即可。根據這裡的一些結果，我們可以在計算過程中不斷取模，避免高精度運算。

經典題目3 

POJ3233 (感謝rmq)

題目大意：給定矩陣A，求A + A^2 + A^3 + … + A^k的結果（兩個矩陣相加就是對應位置分別相加）。輸出的數據mod m。k<=10^9。

這道題兩次二分，相當經典。首先我們知道，A^i可以二分求出。然後我們需要對整個題目的數據規模k進行二分。比如，當k=6時，有：

A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)

應用這個式子後，規模k減小了一半。我們二分求出A^3後再遞歸地計算A + A^2 + A^3，即可得到原問題的答案。

經典題目4 

VOJ1049

題目大意：順次給出m個置換，反覆使用這m個置換對初始序列進行操作，問k次置換後的序列。m<=10, k<2^31。

首先將這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的矩陣很容易構造出來：

 

經典題目7 

VOJ1067

我們可以用上面的方法二分求出任何一個線性遞推式的第n項，其對應矩陣的構造方法為：在右上角的(n-1)*(n-1)的小矩陣中的主對角線上填1，矩陣第n行填對應的係數，其它地方都填0。例如，我們可以用下面的矩陣乘法來二分計算f(n) = 4f(n-1) – 3f(n-2) + 2f(n-4)的第k項：

         

利用矩陣乘法求解線性遞推關係的題目我能編出一卡車來。這裡給出的例題是係數全為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步的路徑數，我們只需要二分求出A^k即可。

經典題目9 

用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M<=5，N<2^31，輸出答案mod p的結果

    

我們以M=3為例進行講解。假設我們把這個矩形橫著放在電腦屏幕上，從右往左一列一列地進行填充。其中前n-2列已經填滿了，第n-1列參差不齊。現在我們要做的事情是把第n-1列也填滿，將狀態轉

-- End --

更多精彩：
☞ 李源潮：我在數學系的日子
☞ 我的博士五年
☞ 為什麼梯度反方向是函數值下降最快的方向？
☞ 7年賺的2個億，數學家6年就花光了，全砸在自家的房子上
☞ 數據科學家最常用的十種算法
☞ 曲面論