题目

阿申准备报名参加 GT 考试，准考证号为 $N$ 位数 $X_1,X_2,…,X_n$ ，他不希望准考证号上出现不吉利的数字。 他的不吉利数字 $A_1,A_2…A_m$ 有 $M$ 位，不出现是指 $X_1,X_2,…,X_n$ 中没有恰好一段等于 $A_1,A_2,…,A_m$ ， $A_1$ 和 $X_1$ 可以为 $0$ 。阿申想知道不出现不吉利数字的号码有多少种，输出模 $K$ 取余的结果。

$N\leq10^9,M\leq20,K\leq1000,0\le X_i,A_i\le9$

分析

设 $f_{i,j}$ 表示文本匹配第 $i$ 位匹配到模式串 $j$ 位时方案数（下标从 $1$ 开始）， $g_{i,j}$ 表示从模式串第 $i$ 位转移到第 $j$ 位的方案数。则有：

$$f_{i,j}=\sum_{k=0}^{m-1}f_{i-1,k}\cdot g_{k,j} $$

不能匹配到 $m$ ，所以答案是 $\sum_{i=0}^{m-1}f_{n,i}$ 。

上面的式子可以用矩阵快速幂优化， $g_{i,j}$ 可以由 KMP 自动机的转移函数 $\mathcal{O}(|\Sigma|m)$ 求。

代码

代码字符串下标从 $0$ 开始。

const int N = 30;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, m, mod;
char s[N];
int fail[N];

struct Matrix {
	int n, m;
	int mat[N][N];
	Matrix() {
		memset (mat, 0, sizeof mat);
	}
	
	int* operator [](int pos) { return mat[pos]; }
	
	Matrix operator *(Matrix b) {
		Matrix c; c.n = n, c.m = b.m;
		for (int i = 1; i <= c.n; i++)
			for (int j = 1; j <= c.m; j++)
				for (int k = 1; k <= c.m; k++)
					(c[i][j] += mat[i][k] * b[k][j] % mod) %= mod;
		return c;
	}
}G;

Matrix operator ^(Matrix a, int b) {
	Matrix ans; ans.n = a.n, ans.m = a.m;
	for (int i = 1; i <= ans.n; i++) ans[i][i] = 1;
	for (; b; b >>= 1, a = a * a)
		if (b & 1) ans = ans * a;
	return ans;
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read(), m = Read(), mod = Read();
	scanf ("%s", s);
	fail[0] = 0;
	for (int i = 1, j = 0; i < m; i++) {
		while (j && s[i] != s[j]) j = fail[j];
		if (s[i] == s[j]) j++;
		fail[i + 1] = j;
	}
	G.n = G.m = m;
	for (int i = 0; i < m; i++) {
		for (char c = '0'; c <= '9'; c++) {
			int j = i;
			while (j && s[j] != c) j = fail[j];
			if (s[j] == c) j++;
			G[i + 1][j + 1]++;
		}
	}
	G = G ^ n;
	int ans = 0;
	for (int i = 1; i <= m; i++) ans = (ans + G[1][i]) % mod;
	printf ("%d\n", ans);
	return 0;
}