acm中矩陣乘法的應(yīng)用精講-wenkub
2023-05-01 12:27:30 本頁面
【正文】 題目4 VOJ1049題目大意：順次給出m個置換，反復(fù)使用這m個置換對初始序列進(jìn)行操作，問k次置換后的序列。然后我們需要對整個題目的數(shù)據(jù)規(guī)模k進(jìn)行二分。輸出的數(shù)據(jù)mod m。這就告訴我們，計(jì)算A^n也可以使用二分快速求冪的方法。預(yù)先把所有m個操作所對應(yīng)的矩陣全部乘起來，再乘以(x,y,1)，即可一步得出最終點(diǎn)的位置。其中翻轉(zhuǎn)是以坐標(biāo)軸為對稱軸進(jìn)行翻轉(zhuǎn)（兩種情況），旋轉(zhuǎn)則以原點(diǎn)為中心。為什么它又滿足結(jié)合律呢？仔細(xì)想想你會發(fā)現(xiàn)這也是廢話。一個n行m列的矩陣可以乘以一個m行p列的矩陣，得到的結(jié)果是一個n行p列的矩陣，其中的第i行第j列位置上的數(shù)等于前一個矩陣第i行上的m個數(shù)與后一個矩陣第j列上的m個數(shù)對應(yīng)相乘后所有m個乘積的和。這幾天連續(xù)看到四個問這類題目的人，今天在這里簡單寫一下。這里我們不介紹其它有關(guān)矩陣的知識，只介紹矩陣乘法和相關(guān)性質(zhì)。比如，下面的算式表示一個2行2列的矩陣乘以2行3列的矩陣，其結(jié)果是一個2行3列的矩陣。假設(shè)你有三個矩陣A、B、C，那么(AB)C和A(BC)的結(jié)果的第i行第j列上的數(shù)都等于所有A(ik)*B(kl)*C(lj)的和（枚舉所有的k和l）。如果對每個點(diǎn)分別進(jìn)行模擬，那么m個操作總共耗時O(mn)。經(jīng)典題目2 給定矩陣A，請快速計(jì)算出A^n（n個A相乘）的結(jié)果，輸出的每個數(shù)都mod p。例如，為了算出A^25的值，我們只需要遞歸地計(jì)算出A^1A^A^3的值即可。k=10^9。比如，當(dāng)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)應(yīng)用這個式子后，規(guī)模k減小了一半。m=10, k2^31。我們可以二分計(jì)算出該矩陣的k/m次方，再乘以初始序列即可。經(jīng)典題目6 給定n和p，求第n個Fibonacci數(shù)mod p的值，n不超過2^31根據(jù)前面的一些思路，現(xiàn)在我們需要構(gòu)造一個2 x 2的矩陣，使得它乘以(a,b)得到的結(jié)果是(b,a+b)。例如，我們可以用下面的矩陣乘法來二分計(jì)算f(n) = 4f(n1) – 3f(n2) + 2f(n4)的第k項(xiàng)：利用矩陣乘法求解線性遞推關(guān)系的題目我能編出一卡車來。類似地，C*A的第i行第j列就表示從i到j(luò)經(jīng)過3條邊的路徑數(shù)。其中前n2列已經(jīng)填滿了，第n1列參差不齊。注意為了保證方案不重復(fù)，狀態(tài)轉(zhuǎn)移時我們不允許在第n1列豎著放一個多米諾骨牌（例如左邊第2種狀態(tài)不能轉(zhuǎn)移到右邊第4種狀態(tài)），否則這將與另一種轉(zhuǎn)移前的狀態(tài)重復(fù)。后面我寫了一份此題的源代碼。題目將給出10個以內(nèi)的病毒片段，每個片段長度不超過10。其中問號表示“其它情況”，它可以是任一字母，只要這個字母不會讓它所在的串成為某個病毒的前綴。例如，從AT不能轉(zhuǎn)移到AA，從AT轉(zhuǎn)移到??有4種方法（后面加任一字母），從?A轉(zhuǎn)移到AA有1種方案（后面加個A），從?A轉(zhuǎn)移到??有2種方案（后面加G或C），從GG到??有2種方案（后面加C將構(gòu)成病毒片段，不合法，只能加A和T）等等。題目中的數(shù)據(jù)規(guī)模保證前綴數(shù)不超過100，一次矩陣乘法是三方的，一共要乘log(n)次。include define SIZE (1m)define MAX_SIZE 32us
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1