acm中矩陣乘法的應(yīng)用精講(編輯修改稿)
2025-05-13 12:27 本頁面
【文章內(nèi)容簡介】 數(shù)，我們只需要二分求出A^k即可。經(jīng)典題目9 用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M=5，N2^31，輸出答案mod p的結(jié)果我們以M=3為例進行講解。假設(shè)我們把這個矩形橫著放在電腦屏幕上，從右往左一列一列地進行填充。其中前n2列已經(jīng)填滿了，第n1列參差不齊?，F(xiàn)在我們要做的事情是把第n1列也填滿，將狀態(tài)轉(zhuǎn)移到第n列上去。由于第n1列的狀態(tài)不一樣（有8種不同的狀態(tài)），因此我們需要分情況進行討論。在圖中，我把轉(zhuǎn)移前8種不同的狀態(tài)放在左邊，轉(zhuǎn)移后8種不同的狀態(tài)放在右邊，左邊的某種狀態(tài)可以轉(zhuǎn)移到右邊的某種狀態(tài)就在它們之間連一根線。注意為了保證方案不重復(fù)，狀態(tài)轉(zhuǎn)移時我們不允許在第n1列豎著放一個多米諾骨牌（例如左邊第2種狀態(tài)不能轉(zhuǎn)移到右邊第4種狀態(tài)），否則這將與另一種轉(zhuǎn)移前的狀態(tài)重復(fù)。把這8種狀態(tài)的轉(zhuǎn)移關(guān)系畫成一個有向圖，那么問題就變成了這樣：從狀態(tài)111出發(fā)，恰好經(jīng)過n步回到這個狀態(tài)有多少種方案。比如，n=2時有3種方案，11101111111110111和111000111，這與用多米諾骨牌覆蓋32矩形的方案一一對應(yīng)。這樣這個題目就轉(zhuǎn)化為了我們前面的例題8。后面我寫了一份此題的源代碼。你可以再次看到位運算的相關(guān)應(yīng)用。經(jīng)典題目10 POJ2778題目大意是，檢測所有可能的n位DNA串有多少個DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四個字符構(gòu)成。題目將給出10個以內(nèi)的病毒片段，每個片段長度不超過10。數(shù)據(jù)規(guī)模n=2 000 000 000。下面的講解中我們以ATC,AAA,GGC,CT這四個病毒片段為例，說明怎樣像上面的題一樣通過構(gòu)圖將問題轉(zhuǎn)化為例題8。我們找出所有病毒片段的前綴，把n位DNA分為以下7類：以AT結(jié)尾、以AA結(jié)尾、以GG結(jié)尾、以?A結(jié)尾、以?G結(jié)尾、以?C結(jié)尾和以??結(jié)尾。其中問號表示“其它情況”，它可以是任一字母，只要這個字母不會讓它所在的串成為某個病毒的前綴。顯然，這些分類是全集的一個劃分（交集為空，并集為全集）?，F(xiàn)在，假如我們已經(jīng)知道了長度為n1的各類DNA中符合要求的DNA個數(shù)，我們需要求出長度為n時各類DNA的個數(shù)。我們可以根據(jù)各類型間的轉(zhuǎn)移構(gòu)造一個邊上帶權(quán)的有向圖。例如，從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）等等。這個圖的構(gòu)造過程類似于用有限狀態(tài)自動機做串匹配。然后，我們就把這個圖轉(zhuǎn)化成矩陣，讓這個矩陣自乘n次即可。最后輸出的是從??狀態(tài)到所有其它狀態(tài)的路徑數(shù)總和。題目中的數(shù)據(jù)規(guī)模保證前綴數(shù)不超過100，一次矩陣乘法是三方的，一共要乘log(n)次。因此這題總的復(fù)雜度是100^3 * log(n)，AC了。最后給出第9題的代碼供大家參考（今天寫的，熟悉了一下C++的類和運算符重載）。為了避免大家看代碼看著看著就忘了，我把這句話放在前面來說：Matrix67原創(chuàng)，轉(zhuǎn)貼請注明出處。include define SIZE (1m)define MAX_SIZE 32using namespace std
教學教案相關(guān)推薦
鄂ICP備17016276號-1