题目链接：BZOJ - 1009
题目分析
题目要求求出不包含给定字符串的长度为 n 的字符串的数量。
既然这样，应该就是 KMP + DP ，用 f[i][j] 表示长度为 i ，匹配到模式串第 j 位的字符串个数，然后转移就是可以从第 j 位加上一个字符转移到另一个位置。
然而..我并没有写过KMP + DP，我觉得还是写AC自动机+DP比较简单..于是，尽管只有一个模式串，我还是写了AC自动机+DP。
然后就是建出AC自动机，f[i][j] 表示长度为 i ，走到节点 j 的字符串的个数。然后 f[i][] 是由 f[i - 1][] 转移过来的。
这个 DP 的转移满足 f[i][j] = sigma(f[i - 1][k] * A[k][j]) ，所以可以用矩阵乘法优化。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime> using namespace std; const int MaxL = 20 + 5; int n, m, Mod, Ans, Root, Zero;
int Child[MaxL][11], Fail[MaxL]; char S[MaxL]; struct Matrix
{
int Num[MaxL][MaxL];
} M; Matrix operator * (Matrix A, Matrix B)
{
Matrix ret;
memset(ret.Num, 0, sizeof(ret.Num));
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
{
if (A.Num[i][j] == 0) continue;
for (int k = 0; k < m; ++k)
{
ret.Num[i][k] += A.Num[i][j] * B.Num[j][k];
ret.Num[i][k] %= Mod;
}
}
return ret;
} Matrix Pow(Matrix a, int b)
{
Matrix ret, f;
memset(ret.Num, 0, sizeof(ret.Num));
for (int i = 0; i < m; ++i) ret.Num[i][i] = 1;
f = a;
while (b)
{
if (b & 1) ret = ret * f;
b >>= 1;
f = f * f;
}
return ret;
} void Prepare()
{
Root = 0;
for (int i = 0; i < m; ++i)
Child[i][S[i + 1] - '0'] = i + 1;
Zero = m + 1;
Fail[Root] = Zero;
for (int i = 0; i <= 9; ++i)
Child[Zero][i] = Root;
for (int i = 0; i < m; ++i)
for (int j = 0; j <= 9; ++j)
if (S[i + 1] - '0' == j) Fail[Child[i][j]] = Child[Fail[i]][j];
else Child[i][j] = Child[Fail[i]][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j <= 9; ++j)
if (Child[i][j] != m)
++M.Num[i][Child[i][j]];
} int main()
{
scanf("%d%d%d", &n, &m, &Mod);
scanf("%s", S + 1);
Prepare();
M = Pow(M, n);
Ans = 0;
for (int i = 0; i < m; ++i)
Ans = (Ans + M.Num[0][i]) % Mod;
printf("%d\n", Ans);
return 0;
}