描述

阿申準備報名參加GT考試，準考證號為N位數(shù)X1X2….Xn(0<=Xi<=9),他不希望準考證號上出現(xiàn)不吉利的數(shù)字。他的不吉利數(shù)學A1A2…Am(0<=Ai<=9)有M位，不出現(xiàn)是指X1X2…Xn中沒有恰好一段等于A1A2…Am. A1和X1可以為0

---

分析

• f[i][j] 表示前i個數(shù)字里匹配到了j位
• 開始想到一個很不完善的方程, f[i][j] = f[i-1][j-1], f[i][0] = sum{f[i-1]}
• 這樣肯定是不對的了, 因為從j-1不一定只能轉移到j, 還有可能換一個數(shù)字后第j位不匹配了但跟原串的其他位還是匹配的.
• 所以要考慮從匹配到第j-1位的狀態(tài)可以轉移到哪些狀態(tài).
• 由此聯(lián)想到KMP里的失配函數(shù). 枚舉第j位的數(shù)字(0..9), 當?shù)趈位失配后, 沿失配指針走直到和枚舉的數(shù)字相同或者失配指針來到0. 如果第k位重新匹配了, 說明j狀態(tài)可以轉移到k狀態(tài), 即第j位放置模板串中第k位的數(shù)字.
• 當然上面的描述有的地方不準確因為沒有明確從0做下標還是從1…
• 有了狀態(tài)轉移方程就可以用矩陣乘法來快速求解. O(m^3 * log(n))
• 根據(jù)矩陣乘法的性質算算看怎么建立矩陣.

---

代碼

https://code.csdn.net/snippets/622317

總結

以上是生活随笔為你收集整理的BZOJ-1009-GT考试-HNOI2008的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。