Border
废话
波论好难，学不懂。
一点一点推罢。
Border 的定义
一个字符串的最长真公共前后缀就叫 Border（这个「真」就表示其不和原字符串相同）。
刨开 Border，剩下的一部分被称作 Period。
Border 是可以有重叠部分的：
为什么剩下的部分要叫 Period？因为它是这个字符串的循环节，Border 没有重叠部分的情况是很显然的。
利用相等关系的传递性，下面三个青色部分是相同的。
所以 Period 是这个串的循环节。 如果还有重叠部分可以一直递归下去。
Border 的性质
令 \(\operatorname{Border}(S)\) 表示字符串 \(S\) 的所有 Border 组成的集合，令 \(\operatorname{maxBorder}(S)\) 表示字符串 \(S\) 长度最大的 Border。
那么有：
就是一个字符串所有的 Border 是由它最大的 Border 和这个 Border 的所有 Border 组成的。
（有重叠的情况懒得画了。）
Border 的前半部分的两段 Border 相同，而 Border 本身的两段也相同，从而前半段的 Border 和后半段的 Border 相同，所以是原字符串的 Border。
由此可见，Border 的 Border 可以利用相等关系的传递性，来证明是原字符串的另一个 Border。
而且并不存在一个 Border，使得它不是 \(\operatorname{maxBorder}(S)\) 且不属于 \(\operatorname{Border}(S)\)。
若存在，则它必定比 \(\operatorname{maxBorder}(S)\) 短，而它又是原串的 Border，所以它分别和 \(\operatorname{maxBorder}(S)\) 的左右两段相同，所以它又是 \(\operatorname{maxBorder}(S)\) 的 Border，矛盾。
如何求每个前缀的 maxBorder
详见 「BJWC2018 Border 的四种求法」一题。
朴素的求法是 \(\mathcal{O}(n^{2})\) 的。
注意到小标题「前缀」这一限定，令 \(nxt_{i}\) 表示 \(\operatorname{maxBorder}(S[1 .. i])\) 的长度（也对应着靠前的 Border 的结束位置）。若我们已知 \(nxt_{1 \sim i - 1}\)，那么可以快速求出 \(nxt_{i}\)。
KMP 包含了这一部分，这里不细讲，贴一个远古博客的链接。
而这个 \(nxt_{i}\) 常常会被称为 \(fail\) 指针，因为在字符串匹配失败时就是利用它快速跳转的。
若把每一对 \((fail_{i}, i)\) 看作一条树上的边，那么所有的边就组成了一棵失配树，总共有 \(n + 1\) 个点和 \(n\) 条边，有时候将题目放到失配树上来做会直观许多。
一个点到根的路径就包含了它所有的 Border。
每一个前缀在 \(S\) 中的出现次数就是其子树大小。
应该还有很多性质，但是还不了解。
习题
做一题写一题，咕咕咕。
Luogu P3193 [HNOI2008] GT考试
考虑对匹配的过程 dp。
观察到 \(M\) 最大只有 \(20\)，所以可以直接以当前匹配长度来作为状态。
令 \(dp_{i, j}\) 表示以第 \(i\) 个字符结束的后缀的最长匹配长度。
令 \(cnt_{i, j}\) 表示在匹配长度为 \(i\) 的后缀后加一个字符使得它最长匹配后缀的长度变为 \(j\) 的方案数。
那么有转移式：
对于每一个 \(i\)，转移的方式都没变，所以可以用矩阵来加速。
如何求 \(cnt_{i, j}\)？直接枚举 \(i\) 和下一个字符，按照 KMP 的方式来进行匹配，假设最后的匹配长度为 \(k\)，那么令 \(cnt_{i, k} \leftarrow cnt_{i, k} + 1\)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, mod, now, ans, nxt[25];
string s;
struct matrix {
int val[20][20];
matrix(int v = 0) {
for(int i = 0; i < m; ++i) {
for(int j = 0; j < m; ++j) {
val[i][j] = (i == j ? v : 0);
}
}
}
void operator *= (const matrix& _) {
static matrix res;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < m; ++j) {
res.val[i][j] = 0;
for(int k = 0; k < m; ++k) {
res.val[i][j] += val[i][k] * _.val[k][j] % mod;
}
res.val[i][j] %= mod;
}
}
memcpy(val, res.val, sizeof(val));
}
} a, res;
matrix ksm(matrix& v, int y) {
matrix ret(1), x = v;
while(y) {
if(y & 1) ret *= x;
x *= x;
y >>= 1;
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> mod >> s;
s = "V" + s;
for(int i = 2, j = 0; i <= m; ++i) {
while(j && s[j + 1] != s[i]) j = nxt[j];
if(s[j + 1] == s[i]) ++j;
nxt[i] = j;
}
for(int i = 0; i < m; ++i) {
for(char j = '0'; j <= '9'; ++j) {
now = i;
while(now && s[now + 1] != j) now = nxt[now];
if(s[now + 1] == j) ++now;
if(now < m) ++a.val[i][now];
}
}
res = ksm(a, n);
for(int i = 0; i < m; ++i) ans += res.val[0][i];
cout << ans % mod;
return 0;
}