先考虑朴素的 dp。
由于涉及到匹配问题，只有一个串，考虑 kmp。
状态表示
设 \(f_{i, j}\) 表示长度为 \(i\) 的字符串，与不吉利串的匹配长度为 \(j\) 的总方案数。
状态转移
枚举待添加的字符 \(c\)，然后计算添加后的最大匹配长度 \(k\)（这里显然 \(k \ge j\)），所以
\[f_{i + 1, k} \leftarrow f_{i + 1, k} + f_{i, j} \]边界条件
\(f_{0, 0} = 1\)
优化
这样 dp 的时间复杂度是 \(\mathcal{O}(nm)\) 的，在本题会超时。
再仔细地分析转移方程，如果我们设 \(a_{j, k}\) 表示从匹配长度为 \(j\) 添加 \(1\) 个字符，匹配长度变为 \(k\) 的方案数，此时状态转移方程变为
\[f_{i + 1, k} = \sum\limits_{j = 0}^{m - 1} f_{i, j} \times a_{j, k} \]这个方程特别像 矩阵乘法，而且这个矩阵 \(A\) 是固定不变的，可以预处理出来。所以考虑矩阵快速幂优化。
就设行向量 \(F_i = \begin{bmatrix} f_{i, 0} & f_{i, 1} & \dots & f_{i, m - 1} \end{bmatrix}\)。
然后很容易可以发现 \(F_{i + 1} = F_i \times A\)。
所以 \(F_n = F_0 \times A^n\)。
时间复杂度
预处理 \(A\) 复杂度 \(\mathcal{O}(m)\)，矩阵快速幂 \(\mathcal{O}(\log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;
const int N = 25;
int n, m, P;
char str[N];
int ne[N];
int a[N][N];
void mul(int c[][N], int a[][N], int b[][N])
{
static int t[N][N];
memset(t, 0, sizeof t);
for (int i = 0; i < m; i ++ )
for (int j = 0; j < m; j ++ )
for (int k = 0; k < m; k ++ )
t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % P;
memcpy(c, t, sizeof t);
}
int qpow(int k)
{
int f0[N][N] = {1};
while (k)
{
if (k & 1) mul(f0, f0, a);
mul(a, a, a);
k >>= 1;
}
int res = 0;
for (int i = 0; i < m; i ++ )
res = (res + f0[0][i]) % P;
return res;
}
int main()
{
cin >> n >> m >> P >> str + 1;
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && str[i] != str[j + 1]) j = ne[j];
if (str[i] == str[j + 1]) j ++ ;
ne[i] = j;
}
for (int j = 0; j < m; j ++ )
for (int c = '0'; c <= '9'; c ++ )
{
int k = j;
while (k && c != str[k + 1]) k = ne[k];
if (c == str[k + 1]) k ++ ;
if (k < m) a[j][k] ++ ;
}
cout << qpow(n) << endl;
return 0;
}