题意
字符串由0-9组成，每一位可以是0-9的任何一个数。
并且要求字符串不包含另一个给定的字符串，求方案数。
题解
一开始以为是数位dp，然后发现是一个dp。
设(f[i][j])为前(i)个字符，最后(j)个字符与目标串匹配的方案数。
我们可以枚举下一个字符，考虑下一个字符会对匹配产生什么影响。
- 匹配下一个字符，从(j)匹配到(j+1)
- 无法匹配下一个字符，到之前找匹配
到之前找匹配的这个过程与kmp很像，其实就是不停的跳(nxt)，不过其实第一个也就是kmp，转移的时候就不停跳匹配就行。
但是(nle 10^{12})，枚举肯定会爆炸。
注意到每一步的转移都是一样的，因为(nxt)的转移只跟(j)有关，而对于每个(i)都是重复的递推。
那么就可以用矩阵优化递推。
[f[i][j] = sum _{k = 0}^{kle m - 1} f[i][k] * g[k][j]
]
(g[i][j])表示末尾匹配到(i)时，有多少种取法使得末尾匹配到(j)。
(g)数组可以在kmp的同时顺便求出来。
这样只要把(g)数组自乘(n)次即可，同时(f)数组的初始条件为(f[0][0] = 1)，只要取(g)数组的第(0)行即可。
#include <bits/stdc++.h>
#define Mid (l + r << 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define int long long
using namespace std;
int read() {
char c; int num, f = 1;
while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0';
while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
return f * num;
}
int n, m, mod;
int a[29], nxt[29];
struct Mat {
int g[29][29];
} A, B;
Mat operator * (const Mat &A, const Mat &B) {
Mat C;
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
C.g[i][j] = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < m; j++) {
for(int k = 0; k < m; k++) {
C.g[i][j] = (C.g[i][j] + A.g[i][k] * B.g[k][j] % mod) % mod;
}
}
}
return C;
}
signed main()
{
n = read(); m = read(); mod = read();
for(int i = 1; i <= m; i++)
scanf("%1d", &a[i]);
int j = 0;
for(int i = 2; i <= m; i++) {
while(j && a[j + 1] != a[i]) j = nxt[j];
if(a[j + 1] == a[i]) j++;
nxt[i] = j;
}
for(int i = 0; i < m; i++) {
for(int p = 0; p <= 9; p++) {
int j = i;
while(j && a[j + 1] != p) j = nxt[j];
if(a[j + 1] == p) j++;
A.g[i][j]++;
}
}
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
B.g[i][j] = (i == j) ? 1 : 0;
int x = n;
for( ; x; x >>= 1, A = A * A)
if(x & 1)
B = A * B;
int ans = 0;
for(int i = 0; i < m; i++)
ans = (ans + B.g[0][i]) % mod;
printf("%lld
", ans);
return 0;
}