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:


Sample Output:


题解:


标题这么引人注意的题目怎么能够不做一下呢?

我们设f[i][j]表示准考证号到i最后一位匹配到不吉利数字j位的方案数。

构造一个矩阵 \(\begin{vmatrix} f[i][0] \\ f[i][1] \\ \vdots \\ f[i][m-1] \end{vmatrix}\)

注意到我们需要再构造一个m*m的矩阵转移到下一矩阵: \(\begin{vmatrix} f[i+1][0] \\ f[i+1][1] \\ \vdots \\ f[i+1][m-1] \end{vmatrix}\)

这个m*m的矩阵构造比较复杂,具体要使用到KMP

我们考虑f[i][j],若第i+1位和j+1位刚好相同,则向f[i+1][j+1]转移,如果第i+1位和fail[j]+1位正好相同,向f[i+1][fail[j]]转移,如果仍然不相同,继续跳fail指针。

根据f[i][j]的转移找到m*m矩阵中具体的位置然后加1。

代码如下: