BZOJ 1009: [HNOI2008]GT考试(KMP+矩阵快速幂加速dp+字符串上的dp)

Description

  阿申准备报名参加GT考试,准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2…Am(0<=Ai<=9)有M位,不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为
0

Input

  第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

Output

  阿申想知道不出现不吉利数字的号码有多少种,输出模K取余的结果.

Sample Input

4 3 100
111

Sample Output

81
这道题目做了很久,之前一直没写过字符串上的dp的问题,也因为我是个字符串和dp的弱者。其实这道题目一眼看出来肯定是字符串匹配搞一下,但是我想的是暴力跑一下AC自动机,但是O(n)肯定不行的。于是开始搜题解,看了一些题解后才明白该怎么做。
首先设为匹配完了前i个字符,且匹配上了长度为j的不吉利数字串的前缀(也就是说从i-j+1到j对应不吉利数字串从a[1]到a[j]的数字)的方案数。那么显然.
那么现在需要思考的是如何递推而来。直观来说对于
解释一下,意味着从匹配了k个字符到匹配了j个字符的方案数。其实看定义就明白了这个aa数组是可以用kmp预处理next数组,然后枚举一下m位0-9的数字跑一跑kmp搞出来的。
但就算这样O(N)的递推还是不可以的。
其实再看一下上面那个式子,是一个齐次递推式子,那么就矩阵快速幂了。把dp数组也弄成矩阵,也就是DP矩阵的第一行对应dp[k]即可。那么快速幂计算矩阵的n次方后,计算一下第一行的和即可。注意初始化dp[0][0]=1。因为一开始匹配到第0个字符的匹配上了0个字符的方案肯定为1,剩余的都为0.
其实感觉字符串上的dp,最难的就是那部分dp状态的设计思想吧。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注