$$f[i][j]=\sum_{k=0}^{m-1} f[i-1][k]*g[k][j]$$
$DP$套$DP$？
其实没那么麻烦，对于第二个的方案数，因为我们知道短串，这个“$g[i][j]$”是固定的，就可以预处理出结果。
为了计算长度为$j$的已经匹配好了的串可以用多少种数字变为$k$，枚举一个数字，看它在短串中最长可以匹配到最多多长的前缀。
妈妈我会$Kmp$！
然后为了保证是最长的而且前面的东西保留，暴力枚举的复杂度好像有点爆炸，这个时候一看不就是一个裸$Kmp$吗，对于新的数字，失去匹配就跳$next$。
于是就得到了一个$O(n*m^2)$的优秀算法....
大概可以做$n<=250000$的数据，然后得到$40$分
### 0x03 矩阵快速幂
然后看一看$DP$式
$$f[i][j]=\sum_{k=0}^{m-1} f[i-1][k]*g[k][j]$$
这不就是一个矩阵乘法的式子吗...
因为$g[i][j]$是固定的，于是把$f[i][j]$看成一个矩阵，对于矩阵$F[i]$它的第一层就是$f[i][j]$。
$$F[i]=F[i-1]*G$$
$G$是固定的，你又知道$F[0]$的第一行第一列是$1$，然后求一个$F[n]$就行了...
矩阵快速幂即可....
### 0x04 代码
暴力
```
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
const int maxn = 1e5 + 10;
int n, m, k;
int ans = 0;
typedef unsigned long long ull;
ull ha_m;
ull mod = 19260817;
ull base = 266;
ull ha[maxn], pw[maxn];
int s[maxn];
char md[maxn];
inline void build(){
ha[0] = 0;
for (int i = 1; i <= n; ++i)
ha[i] = (ha[i - 1] * base + s[i]) % mod;
}
inline ull split(int l, int r){
return ((ha[r] - (ha[l - 1] * pw[r - l + 1]) % mod) + mod) % mod;
}
inline void dfs(int x){
if (x == n + 1){
build();
for (int i = 1; i + m - 1 <= n; ++i){
if (split(i, i + m - 1) == ha_m) return;
}
ans++;
return;
}
for (int i = 0; i <= 9; ++i){
s[x] = i;
dfs(x + 1);
}
}
int main(){
// freopen("data.txt", "r", stdin);
n = read(), m = read(), k = read();
if (n >= 10) return 0 * puts("NO");
scanf("%s", md + 1);
pw[1] = base;
for (int i = 2; i <= n; ++i) pw[i] = (pw[i - 1] * base) % mod;
for (int i = 1; i <= m; ++i) ha_m = (ha_m * base + (md[i] - '0')) % mod;
dfs(1);
printf("%d", ans % k);
return 0;
}
```
40分DP
```
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
const int maxn = 1e6+10;
int f[maxn][30], n, m, k;
int nxt[50], match[50][50];
char md[50];
inline void Inittt(){
n = read(), m = read(), k = read();
scanf("%s", md + 1);
}
inline void Kmp(){
nxt[0] = -1;
for (int i = 1; i <= m; ++i){
int j = nxt[i - 1];
while (j != -1 && md[j + 1] != md[i]) j = nxt[j];
nxt[i] = j + 1;
}
nxt[0] = 0;
for (int i = 0; i < m; ++i){
for (int j = '0'; j <= '9'; ++j){
int temp = i;
while (md[temp + 1] != j && temp > 0) temp = nxt[temp];
if (md[temp + 1] == j) temp++;
if (temp < m) match[i][temp]++;
}
}
}
int main(){
Inittt();
Kmp();
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < m; ++j)
for (int p = 0; p < m; ++p)
{ (f[i][j] += f[i - 1][p] * match[p][j]) %= k; }
int ans = 0;
for (int i = 0; i < m; ++i) (ans += f[n][i]) %= k;
printf("%d", ans);
return 0;
}
```
100分代码（人傻大常数大
```
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}
const int maxn = 5050;
int f[maxn][30], n, m, k;
int nxt[maxn], match[maxn][50];
char md[maxn];
inline void Kmp(){
nxt[0] = -1;
for (int i = 1; i <= m; ++i){
int j = nxt[i - 1];
while (j != -1 && md[j + 1] != md[i]) j = nxt[j];
nxt[i] = j + 1;
}
nxt[0] = 0;
for (int i = 0; i < m; ++i){
for (int j = '0'; j <= '9'; ++j){
int temp = i;
while (md[temp + 1] != j && temp > 0) temp = nxt[temp];
if (md[temp + 1] == j) temp++;
if (temp < m) match[i][temp]++;
}
}
}
class MARTIX{
public:
int mr[23][23];
MARTIX(){ memset(mr, 0, sizeof(m)); }
void pr(){ for (int i = 0; i <= m; i++, cerr << endl) for (int j = 0; j <= m; ++j) cerr << mr[i][j] << " "; }
MARTIX operator * (MARTIX B){
MARTIX Rtn;
memset(Rtn.mr, 0, sizeof(Rtn.mr));
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
for (int p = 0; p < m; ++p)
{ (Rtn.mr[i][j] += mr[i][p] * B.mr[p][j]) %= k; }
return Rtn;
}
}F, G;
inline MARTIX ksm(MARTIX A, int pw){
MARTIX Rtn;
for (int i = 0; i <= m; ++i)
Rtn.mr[i][i] = 1;
for (; pw; pw >>= 1, A = A * A)
if (pw & 1) Rtn = Rtn * A;
return Rtn;
}
signed main(){
n = read(), m = read(), k = read(); scanf("%s", md + 1);
Kmp();
F.mr[0][0] = 1;
for (int i = 0; i <= m; ++i)
for (int j = 0; j <= m; ++j)
G.mr[i][j] = match[i][j];
G = ksm(G, n);
F = F * G;
int ans = 0;
for (int i = 0; i < m; ++i) { (ans += F.mr[0][i]) %= k; }
printf("%d", ans);
return 0;
}
```