KMP + 矩阵快速幂。
首先考虑暴力 DP。
设计状态 $f_{i,j}$ 为长串匹配 $i$ 位，短串最多匹配 $j$ 位时的方案数。
易得转移方程式 $ f_{i,j}=\sum_{k=j}^{m-1} f_{i-1,k}\times g_{k,j}$。
很明显 $g$ 数组是不变的，并且可以通过 KMP 预处理出。
这时我们再观察数据范围 $n$ 很大， $m$ 很小并且 $g$ 数组是不变的，于是我们考虑使用 矩阵快速幂。
我们的 $g$ 数组就是我们的构造矩阵，此时直接套上矩阵快速幂即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10010;
int n,m,mod,ans;
int a[maxn],ne[maxn];
int g[maxn][50];
struct Matrix
{
int s[21][21];
Matrix(){memset(s,0,sizeof(s));}
};
Matrix operator*(const Matrix a,const Matrix b)
{
Matrix c;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
for(int k=0;k<m;k++)
c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%mod;
return c;
}
void KMP()
{
for(int i=2;i<=m;i++)
{
int j=ne[i-1];
while(a[j+1]!=a[i]&&j)j=ne[j];
if(a[j+1]==a[i])ne[i]=j+1;
}
for(int i=0;i<m;i++)
for(int j=0;j<=9;j++)
{
int temp=i;
while(temp&&a[temp+1]!=j)temp=ne[temp];
if(j==a[temp+1])temp++;
g[i][temp]++;
}
}
Matrix quickpow(Matrix a,int k)
{
Matrix sum;
for(int i=0;i<m;i++)
sum.s[i][i]=1;
while(k)
{
if(k&1)sum=sum*a;
a=a*a;
k>>=1;
}
return sum;
}
int main()
{
cin>>n>>m>>mod;
for(int i=1;i<=m;i++)
scanf("%1d",a+i);
KMP();
Matrix a,b;
a.s[0][0]=1;
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
b.s[i][j]=g[i][j];
a=a*quickpow(b,n);
for(int i=0;i<m;i++)
ans=(ans+a.s[0][i])%mod;
cout<<ans;
return 0;
}
|