Description

阿申准备报名参加GT考试，准考证号为N位数 X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai& lt;=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位为不吉利的数字的前j位。

转移方程：

    

 

 

因此就可以使用矩阵乘法加速了！

a[k][j]表示f[i-1][k]转为f[i][j]的方法数,这步可以用KMP解决。

ans+=f[0][j] (j=0;j<m;++j);

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 //ifstream fin("fin.in"); 8  9 string s;10 int n,m,mod,ans=0,pi[25];11 int f[25][25]={
   0},a[25][25],b[25][25];12 13 void Work(int x){14      if(x>3) Work(x/2);15      if(x==1) return ;16      17      memset(a,0,sizeof(a));18      for(int i=0;i
          
           >n>>m>>mod>>s;61 s=" "+s;62 Kmp();63 64 Prepare();65 66 Work(n);67 68 for(int i=0;i