我们用DP来解决这个问题
W[I,J]表示准考证的第I位,和不吉利的数匹配到了第J位的方案数,这个状态的表示也可以看成
当前到第I位了,准考证的后J位是不吉利的数的前J位,的方案数
那么我们最后的ans=ΣW[N,I] 0<=I<=M-1
那么我们考虑怎么转移
假设当前到第I位了,匹配到第J位,也就是W[I,J]的值我们有了,我们可以枚举第I+1位是什么,
然后通过KMP的NEXT数组可以快速的得到当前枚举的位可以匹配到第几位,假设可以匹配到第P位,
那么我们W[I+1,P]+=W[I,J],这样就可以转移了
但是我们看N的数据范围是10^9,所以递推是完不成的,这时候需要观察下规律
我们发现转移时的P,J和I是没有关系的,也就是不管I是几,W[I,J]固定会加到W[I+1,K]上
所以我们换一种转移的方式,之前是用W[I,J]更新W[I+1,P],现在我们可以写成
W[I,J]=a0*W[I-1,0]+a1*W[I-1,1]+......+a(m-1)*W[I-1,M-1]
而且ai数组是不变的,那么这个式子就是常系数线性齐次递推式(新买的书上把这个式子叫这个。。),
然后我们可以用矩阵乘法加速,在log级别中求出ans
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
type
rec =array[..,..] of longint;
var
s :ansistring;
pre :array[..] of longint;
n, m, d39 :longint;
sum, ans :rec;
cur :longint;
procedure init;
var
i, j, k :longint;
c :ansistring;
begin
readln(n,m,d39);
readln(s);
j:=;
for i:= to m do
begin
while (s[i]<>s[j+]) and (j<>) do j:=pre[j];
if s[i]=s[j+] then
begin
inc(j);
pre[i]:=j;
end;
end;
for i:= to m- do
for j:= to do
begin
str(j,c);
k:=i;
while (s[k+]<>c) and (k<>) do k:=pre[k];
if s[k+]=c then inc(k);
inc(sum[i,k]);
end;
end;
function mul(a,b:rec):rec;
var
i, j, l :longint;
begin
fillchar(mul,sizeof(mul),);
for i:= to m- do
for j:= to m- do
for l:= to m- do mul[i,j]:=(mul[i,j]+a[i,l]*b[l,j]) mod d39;
end;
procedure main;
var
p :longint;
i :longint;
begin
for i:= to m do ans[i,i]:=;
p:=n;
while p<> do
begin
if p mod = then ans:=mul(ans,sum);
p:=p div ;
sum:=mul(sum,sum);
end;
for i:= to m- do cur:=(cur+ans[,i]) mod d39;
writeln(cur);
end;
begin
init;
main;
end.