Problem 1009. -- [HNOI2008]GT考试

1009: [HNOI2008]GT考试

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 3773  Solved: 2314

[][][]

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[i][j]=a0*dp[i-1][0]+a1*dp[i-1][1]+a2*dp[i-1][2]+a3*dp[i-1][3]+.......an*dp[i-1][m-1];

 最终有ans=dp[n][0]+dp[n][1]+dp[n][2]+....dp[n][m-1];

dp[i][j]的意思是前i个数组元素的后缀有j个和所要匹配的字符串相同。

首先说明这个递推关系式是正确的：将所有合法的号码按   字符串的尾缀与不合法字符串的前缀  相同元素的个数分类，满足不重不漏关系，所以DP是对的。

然后关系式为线性关系，所以可以用矩阵快速幂来计算。

剩下的问题就是如何求得a0,a1,a2....an（系数矩阵）。

进行一遍for循环范围为i=0----m-1，可以知道i只能对i+1之前的元素产生影响,然后再进行填数字。再由KMP进行确定系数。

 

 

#include
      
       #include
       
        #include
        
         using namespace std;int n,m,mod;int next[25],num[25];void get(){    int i=0,j=-1;    next[0]=-1;    while(i
         
          >=1;        a=mult(a,a);    }    return r;}int main(){   scanf("%d%d%d",&n,&m,&mod);   getchar();   for(int i=0;i