【bzoj1009】[HNOI2008]GT考试

2014年5月9日5,0185

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位的数。 100%数据N<=10^9,M<=20,K<=1000 40%数据N<=1000 10%数据N<=6

Output

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

Sample Input

4 3 100
111

Sample Output

81

题解

矩阵乘法的题题解写起来都十分麻烦。。

而且很多东西只能意会。。

f[i , j]表示前 i 个准考证号匹配到不吉利串第 j 个的方案

然后你需要把一个答案矩阵f[i , j]转移到f[i+1 , j]

举个例子,样例,比如当前匹配到了第2位,也就是说前 i 位的结尾是11

对于第 i+1 个字符,如果是 1 的话,接着匹配到不吉利串第 3 位,不是 1 的话就匹配到第 0 位了

也就是说前 i 位匹配到了不吉利串 j 位,加入 i+1 这个字符,有不同情况,有一些会转移到j+1,一些会转移到其他的,写成一些形如f[i+1 , k] += f[i , j]的式子……

f[i+1 , 3] += f[i , 2]

f[i+1 , 0] += f[i , 2]

即枚举i+1可能出现的字符,然后看n个f[i , j]分别转移到哪去,就在转移矩阵的这个转移路径上+1

按照这个思路用kmp写出转移矩阵,事实上暴力应该就行了

  • YJZ2015年10月25日 下午11:44 回复

    渣渣来膜拜。。

    #1  
  • orz2016年1月3日 下午3:07 回复

    算最后的ans的时候 为什么将a[i,0]累加呢。。在原DP中不应该是加上f[n,0..m-1]?

    #2  
    • hzwer2016年1月3日 下午4:22 回复
      admin

      a矩阵是初始矩阵,乘上了转移矩阵b

      #21
  • Flandre·Scarlet2016年3月5日 下午8:57 回复

    从dp方程转为矩阵乘法个人觉得不是问题关键。希望黄学长(如果还能再发题解的话)能把dp分析写得更详细些。

    #3  
    • hzwer2016年3月6日 上午12:49 回复
      admin

      这个题解我重写过一次了。。。
      确实不好理解
      我再改改看。?

      #31