设f[i,j]为准考证号上第i位匹配到不吉祥数字第j位的方案数,显然j∈[0,m-1]

下面我们就要想到怎么把f[i-1]转移到f[i]

也就是当前匹配到第k位，那么下一位可能会匹配到哪一位

显然我们可以穷举下一位的字符，利用KMP求出下一位会匹配到哪一位（KMP的失配思想）

然后可以得出f[i,j]=f[i-1,0]*w[0,j]+f[i-1,1]*w[1,j]……+f[i-1,m-1]*w[m-1,j]

w[x,y]表示下一位取值能使由上一位匹配到y转移到下一位配到x的数目

然后就是矩乘+快速幂了（感觉解释的很不清楚……）

1 var a,b,c,w:array[0..20,0..20] of longint; 2     next,d:array[0..40] of longint; 3     n,m,p,i,j,k,ans:longint; 4     s:ansistring; 5     ch:char; 6  7 procedure mul; 8   var i,j,k:longint; 9   begin10     for i:=0 to m-1 do11       for j:=0 to m-1 do12       begin13         c[i,j]:=0;14         for k:=0 to m-1 do15           c[i,j]:=(c[i,j]+a[i,k]*b[k,j] mod p) mod p;16       end;17   end;18 19 begin20   readln(n,m,p);21   readln(s);22   for i:=2 to m do23   begin24     while (j<>0) and (s[i]<>s[j+1]) do j:=next[j];25     if s[i]=s[j+1] then26     begin27       inc(j);28       next[i]:=j;29     end;30   end;31   for i:=0 to m-1 do32     for j:=0 to 9 do33     begin34       ch:=chr(j+48);35       k:=i;36       while (k<>0) and (s[k+1]<>ch) do k:=next[k];37       if s[k+1]=ch then inc(k);38       inc(w[k,i]);39     end;40 41   for i:=0 to m-1 do42     c[i,i]:=1;43   j:=0;44   while n>0 do45   begin46     inc(j);47     d[j]:=n mod 2;48     n:=n shr 1;49   end;50   for i:=j downto 1 do51   begin52     a:=c;53     b:=c;54     mul;55     if d[i]=1 then56     begin57       a:=c;58       b:=w;59       mul;60     end;61   end;62   for i:=0 to m-1 do63     ans:=(ans+c[i,0]) mod p;64   writeln(ans);65 end.