形式化题目

给定整数 $n, m, K$ 与一个由 $m$ 个十进制数字组成的串 $A = A_1A_2\cdots A_m$（$A_i \in \{0,\dots,9\}$，允许前导 $0$），统计满足以下条件的数字串 $X = X_1X_2\cdots X_n$ 的个数：

即 $X$ 中不存在下标 $p$ 使 $X_pX_{p+1}\cdots X_{p+m-1} = A$。答案对 $K$ 取模后输出。

注意长度必须恰好为 $n$（含前导 $0$），且 $X_1$ 与 $A_1$ 都可以是 $0$——本题不排除前导零，整个搜索空间是 $10^n$。

数据范围：$1 \leqslant n \leqslant 10^9$，$1 \leqslant m \leqslant 20$，$2 \leqslant K \leqslant 1000$。

暴力解法

思路

把号码从左到右一位一位地考虑，维护一个数 $q$：当前已经匹配了 $A$ 的前 $q$ 位，也就是"$X$ 当前后缀中，是 $A$ 前缀的最长的那一段"的长度。

每读入一位数字 $d$，$q$ 就按 KMP 的规则更新为新长度 $q'$。只要某一步 $q' = m$，说明 $A$ 完整出现，这个号码不合要求，直接丢弃。

关键观察是：$q$ 已经把"过去"中一切有用的信息压缩完了。判断未来会不会凑出 $A$，只需要知道当前最长匹配了 $A$ 的前几位，更久远的历史不再有用。因此 $q$ 是一个合适的 DP 状态，长度分层就是一个自然的 DP。

设 $f_{i,q}$ 表示长度为 $i$、从未出现 $A$、且当前匹配长度为 $q$ 的号码数，则

答案 $= \sum_{q=0}^{m-1} f_{n,q}$。

代码

本题不提供暴力代码文件（任务要求 --no-brute --no-gen，教学上只需理解状态定义与转移，brute.cpp 并非必要），完整可运行实现见下方正解的 main.py；暴力解法不单独给出代码。

复杂度

时间 $O(nm)$（每位枚举 $q$ 与 $d$，$d$ 固定 10 种），空间 $O(m)$。

瓶颈

瓶颈不在 $m$（只有 20），而在 $n$ 可以是 $10^9$：$O(nm) \approx 2\times 10^{10}$ 次运算，任何语言都无法在 1 秒内完成。真正的耗时来源就是"逐位推进 $n$ 次"这个循环本身。

正解

思路

一句话本质：转移规则与位数 $i$ 无关，每一步都在做同一个线性变换，于是"做 $n$ 次变换"可以打包成"求变换的 $n$ 次幂"。

第一步：看清状态转移的结构。

对固定的 $i$，$f_{i+1}$ 的每个分量都是 $f_i$ 各分量的固定线性组合。例如当 $A=$111 时，$f_{i+1,0} = 9f_{i,0} + 9f_{i,1} + 9f_{i,2}$——任何状态下只要读入的不是 1，匹配长度就清零，这样的数字有 9 个。

只要系数与 $i$ 无关，就能把递推写成矩阵形式。记 $v^{(i)}$ 为行向量 $(f_{i,0}, f_{i,1}, \dots, f_{i,m})$，$T$ 为 $(m+1)\times(m+1)$ 的转移矩阵，其中

则 $v^{(i)} = v^{(i-1)}T$，反复代入得

$v^{(0)}$ 的含义是：还没填任何位时，匹配长度必然是 0，方案数 1。

第二步：怎样填出 $T$。

$T[q][q']$ 的构造就是 KMP 自动机：从当前匹配长度 $q$ 出发读数字 $d$，

1. 若 $q>0$ 且 $A_q \neq d$，说明"继续延长当前匹配"走不通，于是沿失配指针回退 $q \leftarrow \text{fail}[q]$，直到回退到一个能让 $A_q = d$ 的前缀；
2. 回退停止后，若 $A_q = d$ 则新长度 $q' = q+1$（成功多匹配一位），否则 $q' = 0$（一位都没匹配上）；
3. 只有当 $q' < m$ 时才把这条转移记进 $T[q][q']$——$q'=m$ 意味着不吉利数字已经出现，这条路径必须被排除。

状态 $m$ 是吸收态（一旦进入就出局），所以矩阵的第 $m$ 行全为 0，后面不必再清理。

下面用样例 A = $ `111` 走一遍。它的失配数组是 `fail = [0, 0, 1, 2]`（`fail[i]` 表示 $A 前 $i$ 位的最长真前后缀长度，例如 11 的最长真前后缀是 1，故 fail[2] = 1）。四个状态与读入 1 时的走向如下：

graph LR
    q0["q=0<br/>（未匹配）"] -->|"读 1"| q1["q=1<br/>后缀 1"]
    q1 -->|"读 1"| q2["q=2<br/>后缀 11"]
    q2 -->|"读 1"| q3["q=3<br/>出现 111"]
    q1 -.->|"读非 1，失配回退"| q0
    q2 -.->|"读非 1，失配回退"| q0
    q0 -->|"读非 1"| q0
    style q3 fill:#fdd,stroke:#c00

观察重点：只有读入 1 才会沿主链前进一位，读入其余 9 个数字都会把匹配长度清零；红色的 $q=3$ 是吸收态，一旦到达就代表号码含 111，不再计数。回退虚线体现了 fail 链的作用：$q=2$ 失配时先退到 fail[2] = 1（后缀 1 仍是 A 的前缀），但此时要接的新数字仍不是 1，于是继续退到 fail[1] = 0，最终匹配长度归零。

据此填出转移矩阵（行 = 当前 $q$，列 = 读一位后的 $q'$，格值 = 能做到这件事的数字个数）：

读表方法：$q=0$ 行中，读非 1 的 9 个数字留在 $q'=0$，读 1 进入 $q'=1$；$q=1$ 行同理，读 1 前进到 $q'=2$，其余 9 个回到 $q'=0$；$q=2$ 行中，读 1 会变成 $q'=3$（被丢弃，所以该格不出现），其余 9 个数字回到 $q'=0$，故整行只有 9。最后一行全 0，正是吸收态。

第三步：用矩阵快速幂处理 $n \le 10^9$。

把 $n$ 按二进制分解，反复平方 $T$（$T^2, T^4, T^8, \dots$），只把二进制为 1 的位对应的幂乘进结果，得到 $T^n$，再与 $v^{(0)}$ 相乘。每层矩阵乘法是 $(m+1)^3 \le 21^3 \approx 9\times10^3$ 次乘加，共 $\log_2 10^9 \approx 30$ 层，总计约 $3\times10^5$ 次运算。

样例验证。 用样例 $n=4,\ m=3,\ A=$111、$K=100$ 逐位推进 $v$（元素依次对应 $q=0,1,2,3$，每一步都已对 $100$ 取模）：

$181 \bmod 100 = 81$，与样例输出一致（若只看累加过程本身：准确计数依次是 $10, 100, 999, 9981$，$9981 \bmod 100 = 81$，与逐步取模的 $181 \bmod 100 = 81$ 等价）。注意第 3 行 $v_0 = 0$：这一步任何不读 1 的号码都会丢掉匹配长度 2，而唯一保持匹配的选择——读 1——会凑齐 111 被剔除，所以长度为 3 的合法号码只剩 99 个。这正是"吸收态被排除"在数据上的直接体现。

代码

build_fail 求失配数组，build_transition 用失配链建出矩阵 $T$，mat_pow 做 $T^n$，solve 完成 $v^{(0)}T^n$ 并输出非吸收态之和。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:55
# update_at: 2026-10-01 00:06

import sys

ALPHABET = range(10)  # 每个 X_i 的取值范围 0..9


def build_fail(pat: list[int]) -> list[int]:
    """pat 的失配指针数组 fail[i]：pat[0:i+1] 的最长真前后缀长度。"""
    fail = [0] * (len(pat) + 1)
    for i in range(1, len(pat)):
        j = fail[i]
        while j and pat[i] != pat[j]:  # 回退到能接上 pat[i] 的最长前缀
            j = fail[j]
        fail[i + 1] = j + 1 if pat[i] == pat[j] else 0
    return fail


def build_transition(pat: list[int], fail: list[int]) -> list[list[int]]:
    """自动机转移矩阵 trans[q][q2]：已匹配 q 位时读入一个数字后匹配到 q2 位的数字个数。

    状态 m 表示"不吉利数字已出现"，是吸收态，题面禁止它出现，故不参与计数。
    """
    m = len(pat)
    trans = [[0] * (m + 1) for _ in range(m + 1)]
    for q in range(m):  # 状态 m 是吸收态，不需要从它出发的转移
        for d in ALPHABET:
            j = q
            while j and pat[j] != d:  # 失配则沿着 fail 链回退
                j = fail[j]
            nxt = j + 1 if pat[j] == d else 0
            if nxt < m:  # 只保留"还没出现完整不吉利数字"的转移
                trans[q][nxt] += 1
    return trans


def mat_mul(a: list[list[int]], b: list[list[int]], mod: int) -> list[list[int]]:
    """模 mod 的矩阵乘法：优化掉零元的稀疏乘，n,m<=20 时比 numpy 更可控。"""
    n, k, m = len(a), len(b), len(b[0])
    out = [[0] * m for _ in range(n)]
    for i in range(n):
        row = out[i]
        for t in range(k):
            if a[i][t]:  # a[i][t] 为 0 时整行贡献为 0，直接跳过
                v = a[i][t]
                b_row = b[t]
                for j in range(m):
                    row[j] = (row[j] + v * b_row[j]) % mod
    return out


def mat_pow(base: list[list[int]], exp: int, mod: int) -> list[list[int]]:
    """矩阵快速幂：对 exp 做二进制分解，反复平方。"""
    size = len(base)
    result = [[int(i == j) for j in range(size)] for i in range(size)]  # 单位矩阵
    while exp:
        if exp & 1:
            result = mat_mul(result, base, mod)
        base = mat_mul(base, base, mod)
        exp >>= 1
    return result


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))          # 号码长度
    m = int(next(it))          # 不吉利数字长度
    mod = int(next(it))        # 模数
    pat = [c - 48 for c in next(it)]  # 不吉利数字的 m 个十进制位（bytes 逐字节减 '0'）

    fail = build_fail(pat)
    trans = build_transition(pat, fail)

    # dp 向量：v[q] = 已经填了 i 位、当前匹配到不吉利数字前 q 位、且从未出现完整串的方案数。
    # 每填一位就是右乘一次 trans，故 n 位后 v = e_0 * trans^n，答案是不含吸收态的全部状态和。
    v = [[1] + [0] * m]  # 初始向量 e_0（行向量），未填任何位时匹配长度必然是 0
    v = mat_mul(v, mat_pow(trans, n, mod), mod)

    print(sum(v[0]) % mod)  # 状态 0..m-1 之和；状态 m 已在建矩阵时排除


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:19
 * update_at: 2026-10-06 00:19
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 25; // m <= 20，矩阵是 (m+1) 阶，开 25 足够

ll n, m, mod;
ll a[MAXM];   // a[i]：不吉利数字的第 i 位（下标从 0 开始），取值 0..9
ll fail[MAXM]; // fail[i]：a[0..i-1] 的最长真前后缀长度（KMP 失配数组）
ll trans[MAXM][MAXM]; // trans[q][q2]：已匹配 q 位时读一个数字变成 q2 位的数字个数
ll base_mat[MAXM][MAXM], result_mat[MAXM][MAXM], tmp_mat[MAXM][MAXM]; // 矩阵幂用的三个方阵
ll v[MAXM];   // v[q]：填了若干位后当前匹配长度为 q 且从未出现完整不吉利数字的方案数

// 求 KMP 失配数组：fail[i] 表示前 i 位的最长相等真前后缀长度。
void build_fail() {
    fail[0] = 0;
    fail[1] = 0;
    for (ll i = 1; i < m; i++) {
        ll j = fail[i];
        while (j && a[i] != a[j]) j = fail[j]; // 回退到还能接上 a[i] 的前缀
        if (a[i] == a[j]) j++;
        fail[i + 1] = j;
    }
}

// 建转移矩阵：从匹配长度 q 出发，对 10 个数字分别求 KMP 转移后的新长度。
// 只统计新长度 q2 < m 的转移；q2 == m 意味着不吉利数字出现，这条路径直接排除。
void build_transition() {
    memset(trans, 0, sizeof(trans));
    for (ll q = 0; q < m; q++) { // 吸收态 m 不需要出边
        for (ll d = 0; d <= 9; d++) {
            ll j = q;
            while (j && a[j] != d) j = fail[j]; // 沿失配链回退
            ll q2 = j + 1;
            if (a[j] != d) q2 = 0;
            if (q2 < m) trans[q][q2]++; // 多少个数字能完成 q -> q2 的转移
        }
    }
}

// 矩阵乘法 c = a * b（mod 意义下），size = m+1。
void mat_mul(ll c[][MAXM], ll x[][MAXM], ll y[][MAXM]) {
    memset(tmp_mat, 0, sizeof(tmp_mat));
    for (ll i = 0; i <= m; i++) {
        for (ll t = 0; t <= m; t++) {
            if (x[i][t] == 0) continue; // 零元整行贡献为 0，跳过
            for (ll j = 0; j <= m; j++) {
                tmp_mat[i][j] = (tmp_mat[i][j] + x[i][t] * y[t][j]) % mod;
            }
        }
    }
    // 结果先写进 tmp_mat，再拷回 c，避免 x 或 y 就是 c 时被覆盖出错
    for (ll i = 0; i <= m; i++) {
        for (ll j = 0; j <= m; j++) {
            c[i][j] = tmp_mat[i][j];
        }
    }
}

// 矩阵快速幂：result_mat = trans^n（mod 意义下），二进制分解反复平方。
void mat_pow() {
    for (ll i = 0; i <= m; i++) {
        for (ll j = 0; j <= m; j++) {
            result_mat[i][j] = (i == j); // 单位矩阵
        }
    }
    memcpy(base_mat, trans, sizeof(trans));
    ll e = n;
    while (e) {
        if (e & 1) mat_mul(result_mat, result_mat, base_mat);
        mat_mul(base_mat, base_mat, base_mat);
        e >>= 1;
    }
}

// 求答案：初始向量 v = e_0，右乘 trans^n，再对非吸收态求和。
void solve() {
    build_fail();
    build_transition();
    mat_pow();

    memset(v, 0, sizeof(v));
    v[0] = 1; // 没填任何位时匹配长度必然是 0，方案数 1

    ll ans = 0;
    for (ll q = 0; q < m; q++) { // 状态 m 是吸收态，不参与计数
        ll sum = 0;
        for (ll t = 0; t <= m; t++) {
            sum = (sum + v[t] * result_mat[t][q]) % mod;
        }
        ans = (ans + sum) % mod;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> n >> m >> mod >> s;
    for (ll i = 0; i < m; i++) {
        a[i] = s[i] - '0'; // 不吉利数字的每一位，允许前导 0
    }

    solve();

    return 0;
}

复杂度

• 时间复杂度：$O(m^3 \log n)$。构造自动机 $O(m^2)$ 量级，矩阵快速幂共 $\log n$ 层、每层 $O(m^3)$。代入 $m \leqslant 20$、$n \leqslant 10^9$：约 $3\times10^5$ 次乘加。
• 空间复杂度：$O(m^2)$，保存常数个 $(m+1)\times(m+1)$ 矩阵，$m=20$ 时不到 400 个整数。实测峰值内存 14.9 MB。

总结

本题的关键不是"数数"，而是找到能把历史压缩成一个数的状态：号码当前后缀与不吉利数字的最长公共前缀长度 $q$。有了 $q$，长度分层 DP 的转移就与位数无关，$n \le 10^9$ 的超长循环随即变成 $O(m^3\log n)$ 的矩阵幂——DP 定状态、KMP 建转移、矩阵幂消 $n$，三步各司其职。两个容易失分的地方：状态 $m$（已出现不吉利数字）必须作为吸收态排除在计数之外；以及前导零是合法的，不能按"首位不能为 0"去砍掉 $9\times10^{n-1}$ 以外的情况。

实测 10 个真实评测点全部通过，最大规模（$n=10^9,\ m=20$）单点耗时约 0.030 s，相对 1000 ms 限时余量充足。