acm中矩陣乘法的應(yīng)用精講-在線瀏覽
2025-06-03 12:27本頁面
【正文】 ）經(jīng)典題目4 VOJ1049題目大意：順次給出m個(gè)置換，反復(fù)使用這m個(gè)置換對(duì)初始序列進(jìn)行操作，問k次置換后的序列。首先將這m個(gè)置換“合并”起來（算出這m個(gè)置換的乘積），然后接下來我們需要執(zhí)行這個(gè)置換k/m次（取整，若有余數(shù)則剩下幾步模擬即可）。例如，將1 2 3 4置換為3 1 2 4，相當(dāng)于下面的矩陣乘法：置換k/m次就相當(dāng)于在前面乘以k/m個(gè)這樣的矩陣。做出來了別忙著高興，得意之時(shí)就是你滅亡之日，別忘了最后可能還有幾個(gè)置換需要模擬。解題方法和上一題類似，都是用矩陣來表示操作，然后二分求最終狀態(tài)。每多乘一次這個(gè)矩陣，這兩個(gè)數(shù)就會(huì)多迭代一次。不用多想，這個(gè)2 x 2的矩陣很容易構(gòu)造出來：經(jīng)典題目7 VOJ1067我們可以用上面的方法二分求出任何一個(gè)線性遞推式的第n項(xiàng)，其對(duì)應(yīng)矩陣的構(gòu)造方法為：在右上角的(n1)*(n1)的小矩陣中的主對(duì)角線上填1，矩陣第n行填對(duì)應(yīng)的系數(shù)，其它地方都填0。這里給出的例題是系數(shù)全為1的情況。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，實(shí)際上就等于從點(diǎn)i到點(diǎn)j恰好經(jīng)過2條邊的路徑數(shù)（枚舉k為中轉(zhuǎn)點(diǎn)）。同理，如果要求經(jīng)過k步的路徑數(shù)，我們只需要二分求出A^k即可。假設(shè)我們把這個(gè)矩形橫著放在電腦屏幕上，從右往左一列一列地進(jìn)行填充?，F(xiàn)在我們要做的事情是把第n1列也填滿，將狀態(tài)轉(zhuǎn)移到第n列上去。在圖中，我把轉(zhuǎn)移前8種不同的狀態(tài)放在左邊，轉(zhuǎn)移后8種不同的狀態(tài)放在右邊，左邊的某種狀態(tài)可以轉(zhuǎn)移到右邊的某種狀態(tài)就在它們之間連一根線。把這8種狀態(tài)的轉(zhuǎn)移關(guān)系畫成一個(gè)有向圖，那么問題就變成了這樣：從狀態(tài)111出發(fā)，恰好經(jīng)過n步回到這個(gè)狀態(tài)有多少種方案。這樣這個(gè)題目就轉(zhuǎn)化為了我們前面的例題8。你可以再次看到位運(yùn)算的相關(guān)應(yīng)用。合法的DNA只能由ACTG四個(gè)字符構(gòu)成。數(shù)據(jù)規(guī)模n=2 000 000 000。我們找出所有病毒片段的前綴，把n位DNA分為以下7類：以AT結(jié)尾、以AA結(jié)尾、以GG結(jié)尾、以?A結(jié)尾、以?G結(jié)尾、以?C結(jié)尾和以??結(jié)尾。顯然，這些分類是全集的一個(gè)劃分（交集為空，并集為全集）。我們可以根據(jù)各類型間的轉(zhuǎn)移構(gòu)造一個(gè)邊上帶權(quán)的有向圖。這個(gè)圖的構(gòu)造過程類似于用有限狀態(tài)自動(dòng)機(jī)做串匹配。最后輸出的是從??狀態(tài)到所有其它狀態(tài)的路徑數(shù)總和。因此這題總的復(fù)雜度是100^3 * log(n)，AC了。為了避免大家看代碼看著看著就忘了，我把這句話放在前面來說：Matrix67原創(chuàng)，轉(zhuǎn)貼請(qǐng)注明出處。/m)class CMatrix{public:long element[MAX_SIZE][MAX_SIZE]。void setModulo(int)。CMatrix power(int)。long modulo。void CMatrix::setSize(int a){for (int i=0。 jelement[i][j]=0。}void CMatrix::setModulo(int a){modulo = a。(size)。for (int i=0。 jfor (int k=0。[i][j]%=modulo。}CMatrix CMatrix
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1