acm中矩陣乘法的應(yīng)用精講-wenkub.com
2025-04-13 12:27 本頁面
【正文】 能干的人，不在情緒上計較，只在做事上認(rèn)真；無能的人！不在做事上認(rèn)真，只在情緒上計較。}寧可累死在路上，也不能閑死在家里！寧可去碰壁，也不能面壁。 [1][1]=0。n==0) break。 while(cin[0][0][0][1]n) { if([0][0]==0amp。 } tm=tm1。j++) for(k=0。 for(i=0。k++) { [i][j]+=([i][k]*[k][j])%MOD。i++) for(j=0。 while(n) { if(namp。i++) for(j=0。 int i,j,k。define N 2define MOD 7struct Matrix{ int m[2][2]。根據(jù)給出的遞推公式可以設(shè)想：然后使用矩陣乘法時間復(fù)雜度為log（n）的一個算法，（模板代碼），具體算法講解可由指數(shù)算法推廣得出。printf(%d, (n).element[SIZE1][SIZE1] )。 k++)isValid=isValid||(iamp。j) == ((~i)amp。(SIZE)。scanf(%d%d%d, amp。else return (exp/2)。}CMatrix CMatrix::power(int exp){CMatrix tmp = (*this) * (*this)。 jfor (int k=0。(size)。 jelement[i][j]=0。long modulo。void setModulo(int)。為了避免大家看代碼看著看著就忘了，我把這句話放在前面來說：Matrix67原創(chuàng)，轉(zhuǎn)貼請注明出處。最后輸出的是從??狀態(tài)到所有其它狀態(tài)的路徑數(shù)總和。我們可以根據(jù)各類型間的轉(zhuǎn)移構(gòu)造一個邊上帶權(quán)的有向圖。我們找出所有病毒片段的前綴，把n位DNA分為以下7類：以AT結(jié)尾、以AA結(jié)尾、以GG結(jié)尾、以?A結(jié)尾、以?G結(jié)尾、以?C結(jié)尾和以??結(jié)尾。合法的DNA只能由ACTG四個字符構(gòu)成。這樣這個題目就轉(zhuǎn)化為了我們前面的例題8。在圖中，我把轉(zhuǎn)移前8種不同的狀態(tài)放在左邊，轉(zhuǎn)移后8種不同的狀態(tài)放在右邊，左邊的某種狀態(tài)可以轉(zhuǎn)移到右邊的某種狀態(tài)就在它們之間連一根線。假設(shè)我們把這個矩形橫著放在電腦屏幕上，從右往左一列一列地進(jìn)行填充。令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)）。不用多想，這個2 x 2的矩陣很容易構(gòu)造出來：經(jīng)典題目7 VOJ1067我們可以用上面的方法二分求出任何一個線性遞推式的第n項，其對應(yīng)矩陣的構(gòu)造方法為：在右上角的(n1)*(n1)的小矩陣中的主對角線上填1，矩陣第n行填對應(yīng)的系數(shù)，其它地方都填0。解題方法和上一題類似，都是用矩陣來表示操作，然后二分求最終狀態(tài)。例如，將1 2 3 4置換為3 1 2 4，相當(dāng)于下面的矩陣乘法：置換k/m次就相當(dāng)于在前面乘以k/m個這樣的矩陣。（有木有感覺很強(qiáng)大？）經(jīng)典
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1