BZOJ1009
妙！
推荐这篇题解： https://www.luogu.org/blog/Edgration/solution-p3193
考虑设计dp，设$f_{i, j}$表示长串匹配到i，短串匹配到j的方案数，初值有$f_{0,0} = 1$
那么最后的答案 $ans = \sum_{i = 0}^{m - 1} f_{n,i}$
考虑转移，假设当前填到第i位，有一种填法能使$f_{i,j}$转移到$f_{i + 1, j + 1}$，那么填剩下的数字全部都转移到$f_{i + 1,0}$吗？
错！这就是一开始想错的地方，填不一样的数字并不一定是转移到0的匹配位置，而是考虑转移到以j结尾的后缀的最长前缀！
设$g_{i, j}$表示从i的匹配长度转移到j的匹配长度的方案数，有转移：
$f_{i, j} = \sum_{k = 0}^{m - 1}f_{i - 1, k} * g_{k, j}$
因为给出的短串是恒定的，所以g数组的值也是恒定的，而找与后缀相匹配的最长前缀，肯定是想到kmp啦
然而这样还是不足以通过本题，再次观察这个方程，发现这就是一个矩阵乘法的形式，相当于把f看成一个1*m的矩阵F，把g看成一个m*m的转移矩阵G。
$F' = F * G^{n}$ 用G转移Fn次
到此为止，本题全部解决，时间复杂度$O(m^{2}logn)$
Code：
#include <cstdio>
#include <cstring>
using namespace std; const int N = ; int n, m, P, nxt[N], mat[N][N];
char str[N]; inline void prework() {
nxt[] = nxt[] = ;
for(int i = , j = ; i <= m; i++) {
for(; j > && str[i] != str[j + ]; j = nxt[j]);
if(str[i] == str[j + ]) j++;
nxt[i] = j;
} for(int i = ; i < m; i++) {
for(int j = ''; j <= ''; j++) {
int tmp = i;
for(; tmp > && str[tmp + ] != j; tmp = nxt[tmp]);
if(str[tmp + ] == j) tmp++;
if(tmp < m) mat[i][tmp]++;
}
}
} inline void work(int &x, int y) {
x = (x + y % P) % P;
} struct Matrix {
int s[N][N]; inline void init() {
memset(s, , sizeof(s));
} friend Matrix operator * (const Matrix &x, const Matrix &y) {
Matrix res;
res.init();
for(int i = ; i < m; i++)
for(int j = ; j < m; j++)
for(int k = ; k < m; k++)
work(res.s[i][j], x.s[i][k] * y.s[k][j]);
return res;
} inline Matrix pow(int y) {
Matrix res = *this, x = *this;
for(y--; y > ; y >>= ) {
if(y & ) res = res * x;
x = x * x;
}
return res;
} } f, g; int main() {
scanf("%d%d%d", &n, &m, &P);
scanf("%s", str + );
prework(); for(int i = ; i < m; i++)
for(int j = ; j < m; j++)
g.s[i][j] = mat[i][j];
g = g.pow(n); f.s[][] = ; f = f * g; int ans = ;
for(int i = ; i < m; i++)
work(ans, f.s[][i]);
printf("%d\n", ans); return ;
}