【正文】 1的各類DNA中符合要求的DNA個數(shù)，我們需要求出長度為n時各類DNA的個數(shù)。其中問號表示“其它情況”，它可以是任一字母，只要這個字母不會讓它所在的串成為某個病毒的前綴。下面的講解中我們以ATC,AAA,GGC,CT這四個病毒片段為例，說明怎樣像上面的題一樣通過構(gòu)圖將問題轉(zhuǎn)化為例題8。題目將給出10個以內(nèi)的病毒片段，每個片段長度不超過10。經(jīng)典題目10 POJ2778題目大意是，檢測所有可能的n位DNA串有多少個DNA串中不含有指定的病毒片段。后面我寫了一份此題的源代碼。比如，n=2時有3種方案，11101111111110111和111000111，這與用多米諾骨牌覆蓋32矩形的方案一一對應(yīng)。注意為了保證方案不重復(fù)，狀態(tài)轉(zhuǎn)移時我們不允許在第n1列豎著放一個多米諾骨牌（例如左邊第2種狀態(tài)不能轉(zhuǎn)移到右邊第4種狀態(tài)），否則這將與另一種轉(zhuǎn)移前的狀態(tài)重復(fù)。由于第n1列的狀態(tài)不一樣（有8種不同的狀態(tài)），因此我們需要分情況進行討論。其中前n2列已經(jīng)填滿了，第n1列參差不齊。經(jīng)典題目9 用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M=5，N2^31，輸出答案mod p的結(jié)果我們以M=3為例進行講解。類似地，C*A的第i行第j列就表示從i到j(luò)經(jīng)過3條邊的路徑數(shù)。經(jīng)典題目8 給定一個有向圖，問從A點恰好走k步（允許重復(fù)經(jīng)過邊）到達B點的方案數(shù)mod p的值把給定的圖轉(zhuǎn)為鄰接矩陣，即A(i,j)=1當(dāng)且僅當(dāng)存在一條邊ij。例如，我們可以用下面的矩陣乘法來二分計算f(n) = 4f(n1) – 3f(n2) + 2f(n4)的第k項：利用矩陣乘法求解線性遞推關(guān)系的題目我能編出一卡車來。那么，我們把這個2 x 2的矩陣自乘n次，再乘以(0,1)就可以得到第n個Fibonacci數(shù)了。經(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īng)典題目5 《算法藝術(shù)與信息學(xué)競賽》207頁（，[例題5]細(xì)菌，版次不同可能頁碼有偏差）大家自己去看看吧，書上講得很詳細(xì)。我們可以二分計算出該矩陣的k/m次方，再乘以初始序列即可。注意任意一個置換都可以表示成矩陣的形式。m=10, k2^31。這題有位強人topsky 說：題目3構(gòu)造一個矩陣A IO I自乘后A^2 I+AO I乘3次為A^3 I+A+A^2O I這樣應(yīng)該會更快吧，直接二分一下。比如，當(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減小了一半。首先我們知道，A^i可以二分求出。k=10^9。經(jīng)典題目3 POJ3233題目大意：給定矩陣A，求A + A^2 + A^3 + … + A^k的結(jié)果（兩個矩陣相加就是對應(yīng)位置分別相加）。例如，為了算出A^25的值，我們只需要遞歸地計算出A^1A^A^3的值即可。我們可以得到這樣的結(jié)論：當(dāng)n為偶數(shù)時，A