1646：GT 考试

题目描述

阿申准备报名参加 GT 考试，准考证号为 $n$ 位数 $X_1 X_2 \cdots X_n (0 \le X_i \le 9)$，他不希望准考证号上出现不吉利的数字。

他的不吉利数字 $A_1 A_2 \cdots A_m (0 \le A_i \le 9)$ 有 $m$ 位，不出现是指 $X_1 X_2 \cdots X_n$ 中没有恰好一段等于 $A_1 A_2 \cdots A_m$，$A_1$ 和 $X_1$ 可以为 $0$。

输入格式

第一行输入 $n, m, K$，接下来一行输入 $m$ 位的数（字符串形式）。

输出格式

阿申想知道不出现不吉利数字的号码有多少种，输出模 $K$ 取余的结果。

样例

样例输入 #1

4 3 100
111

样例输出 #1

81

样例解释 #1

• $n=4$ 位准考证号，不吉利数字为 111（$m=3$），模数 $K=100$。
• 求 $4$ 位数字串中不包含子串 111 的个数，模 $100$。
• 总共有 $10^4 = 10000$ 个可能的号码。包含 111 的号码需要排除。可以计算不包含 111 的号码有 $81$ 个（具体需要动态规划）。
• 输出 $81 \bmod 100 = 81$。

数据范围

对于全部数据：

• $1 \le n \le 10^9$
• $1 \le m \le 20$
• $2 \le K \le 1000$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：$n$ 很大，$m$ 较小，需要利用动态规划与矩阵快速幂加速。这是一个典型的字符串禁止模式计数问题，可以使用 KMP 自动机 + 矩阵快速幂。

设 $dp[i][j]$ 表示构造了前 $i$ 位数字，且当前后缀与不吉利数字匹配长度为 $j$（即再添加一个数字可能形成完整的不吉利数字）的方案数。其中 $j$ 的范围是 $0$ 到 $m-1$（不能达到 $m$，因为达到 $m$ 表示出现了不吉利数字，这是不允许的）。

转移：对于每个状态 $j$，我们添加一个数字 $c$（$0$ 到 $9$），利用 KMP 的 next 数组计算出添加后的匹配长度 $next_j$（即新的 $j'$）。如果 $j' = m$，则说明形成了完整的不吉利数字，应该跳过；否则，转移 $dp[i+1][j'] += dp[i][j]$。

初始状态：$dp[0][0] = 1$（还没有任何数字，匹配长度为 $0$）。

最终答案：$\sum_{j=0}^{m-1} dp[n][j]$。

由于 $n$ 可达 $10^9$，不能直接递推。但状态数只有 $m$（最多 $20$），转移是线性的，可以写成矩阵形式。设 $F_i$ 是一个 $m$ 维向量，表示 $dp[i][0..m-1]$。则 $F_{i+1} = F_i \times T$，其中 $T$ 是转移矩阵，$T_{j,k}$ 表示从状态 $j$ 添加一个数字后到达状态 $k$ 的方案数。

具体地，对于每个 $j$ 和每个数字 $c$，计算 $next = go(j, c)$（即 KMP 自动机的转移），如果 $next < m$，则 $T_{j, next}++$（因为添加数字 $c$ 可以从状态 $j$ 转移到状态 $next$）。

那么 $F_n = F_0 \times T^n$，其中 $F_0 = [1, 0, 0, ..., 0]$（只有 $j=0$ 为 $1$）。答案就是 $F_n$ 的所有元素之和。

因此，算法步骤：

1. 读入 $n, m, K$ 和不吉利数字字符串 $s$（长度为 $m$）。
2. 计算 $s$ 的 KMP next 数组（对于匹配长度 $j$，当添加字符 $c$ 时，计算新的匹配长度）。
3. 构建转移矩阵 $T$（大小 $m \times m$）：对于每个 $j$（$0 \le j < m$）和每个数字 $c$（$0$ 到 $9$），计算 $next = go(j, c)$。如果 $next < m$，则 $T[j][next] = (T[j][next] + 1) \bmod K$。
4. 计算 $T^n$（矩阵快速幂）。
5. 计算 $F_n = F_0 \times T^n$（即取 $T^n$ 的第一行，因为 $F_0$ 只有第一维为 $1$）。
6. 答案 $ans = \sum_{j=0}^{m-1} F_n[j] \bmod K$。

注意：$K$ 可能不是质数，但矩阵乘法只需要取模即可。

复杂度：矩阵大小 $m \le 20$，矩阵乘法 $O(m^3)$，快速幂 $O(m^3 \log n)$，可以接受。

KMP 自动机的转移函数 $go(j, c)$：

• 如果 $s[j] == c$，则 $next = j+1$。
• 否则，$next = next[j]$（即 KMP 的 next 值，不断回退直到匹配或为 $0$），然后继续比较 $s[next]$ 和 $c$，直到匹配或 $next=0$。 可以预处理一个二维数组 $go[j][c]$，表示当前匹配长度为 $j$，添加数字 $c$ 后新的匹配长度。

预处理 next 数组：

next[0] = -1;
for (int i = 1, j = -1; i <= m; i++) {
    while (j >= 0 && s[i] != s[j+1]) j = next[j];
    if (s[i] == s[j+1]) j++;
    next[i] = j;
}

注意字符串下标从 $1$ 开始。

然后计算 $go[j][c]$：

for (int j = 0; j < m; j++) {
    for (int c = 0; c <= 9; c++) {
        int k = j;
        while (k >= 0 && s[k+1] - '0' != c) k = next[k];
        if (s[k+1] - '0' == c) k++;
        go[j][c] = k;
    }
}

最后构建转移矩阵 $T$：如果 $go[j][c] < m$，则 $T[j][go[j][c]]++$。

注意：当 $j = m$ 时表示已经匹配了不吉利数字，但我们不会转移到这里，所以不考虑。