「BZOJ1009」[HNOI2008] GT考试

2014年5月9日15,3616

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写出转移矩阵,事实上暴力应该就行了

avatar
4 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
orzorzhzwerFlandre·ScarletorzYJZ Recent comment authors
  Subscribe  
提醒
orzorz
orzorz

请问转移矩阵在前面的时候不会不合法吗。。。比如说dp[i][j]。。如果i的长度小于j的时候呢。。。

Flandre·Scarlet

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

orz
orz

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

YJZ
YJZ

渣渣来膜拜。。