Bzoj 1009
题意：给定$m$长值域$[0,9]$数列$A_i$，要求构造$n$长值域$[0,9]$数列$X_i$使得$A_i$不是$X_i$的子串，即$X_i$中不出现$A_i$，求方案数。$n \leq 10^9, m \leq 20$
类似CF 1096D，CF 1015F以及AC自动机的相关方法，我们这里可以定义$dp(i,j)$为构造串$X_i$前$i$个字符与$A_i$匹配了$j$位的方案数。最后答案即为$\sum_{i=0}^{m-1} dp(n,i)$，即不包含完全匹配的串的方案
转移方程为(刷表)：
$$
dp(i+1,x)+=dp(i,j)
$$
$x$为在当前后面放一个$[0,9]$之间的数后匹配的影响，特别的，如果匹配了$m$位，以后转移都只能从$m$转移而来。这个$x$可用 $KMP$ 预处理。
这里$n \leq 10^9$ 显然矩阵优化，构造矩阵即可。
注意$j=0$处转移矩阵：$dp(i,0)$一定可以以某个$[0,9]$之间的数转移到$dp(i+1, 1)$，所以在矩阵中设$(0,1)=1$;
$dp(i,0)$一定可以有$9$种情况转移到$dp(i+1, 0)$，即仍然不匹配。所以在矩阵中设$(0,0)=1$
发现一个新的 $Debug$ 方法：过不去样例，可以测测自己写的小数据，这个数据可能非常小，如果程序都过不去的话，那么肯定这里都有问题。就能各个击破，发现 $Bug$。
知识点：
1、过不了样例可以测测自己出的小数据
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
LL n, m, p, a[20 + 5], f[20 + 5], whw[20 + 5][10 + 5];
// n 位数. m->a[maxM], f[maxM], whw[maxM][0~9]
struct matrix {
LL x, y, a[20 + 5][20 + 5];
matrix(LL _x, LL _y) {x = _x, y = _y, ms(a, 0);}
};
matrix mul(matrix a, matrix b) {
matrix ret(a.x, b.y);
for (LL i = 0; i <= a.x; ++i) {
for (LL j = 0; j <= b.y; ++j) {
for (LL k = 0; k <= a.y; ++k) {
ret.a[i][j] = (ret.a[i][j] + (a.a[i][k] * b.a[k][j]) % p) % p;
}
}
}
return ret;
}
matrix ksm(matrix a, LL b) {
matrix bs = a, ans(a.x, a.y);
LL fl = 0;
while (b) {
if (b & 1) {
if (!fl) fl = 1, ans = bs; else ans = mul(ans, bs);
}
bs = mul(bs, bs);
b >>= 1;
}
return ans;
}
void clean() {
ms(whw, 0);
}
int solve() {
clean();
scanf("%lld%lld%lld", &n, &m, &p);
for (LL i = 1; i <= m; ++i) scanf("%1lld", &a[i]);
f[1] = f[2] = 1;
for (LL i = 2; i <= m; ++i) {
LL j = f[i];
while (j > 1 && a[i] != a[j]) j = f[j];
f[i + 1] = (a[i] == a[j] ? j + 1 : 1);
}
for (LL i = 1; i <= m; ++i) {
for (LL x = 0; x <= 9; ++x) {
LL j = i;
while (j > 1 && a[j] != x) j = f[j];
whw[i][x] = (a[j] == x ? j : 0);
}
}
matrix gg(m, m), hh(1, m);
gg.a[0][0] = 9;
gg.a[0][1] = 1;
for (LL i = 1; i < m; ++i) {
for (LL x = 0; x <= 9; ++x) {
++gg.a[i][whw[i + 1][x]];
}
}
++gg.a[m][m];
// for (LL i = 0; i <= m; ++i, puts(""))for (LL j = 0; j <= m; ++j) printf("%d ", gg.a[i][j]);
gg = ksm(gg, n);
// for (LL i = 0; i <= m; ++i, puts(""))for (LL j = 0; j <= m; ++j) printf("%d ", gg.a[i][j]);
hh.a[0][0] = 1;
hh = mul(hh, gg);
// for (LL i = 0; i <= m; ++i, puts(""))for (LL j = 0; j <= m; ++j) printf("%d ", hh.a[i][j]);
LL ans = 0;
for (LL i = 0; i < m; ++i) ans = (ans + hh.a[0][i]) % p;
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
2 2 10000000
11
1 1 10000000
1
*/
