题目描述

给定一个正整数 $N$ 和一个正整数 $M$（长度可达 $100$ 位，以字符串形式给出，无前导零），数字 $M$ 被视为不吉利的数字。一个 $N$ 位数（首位不能为 $0$，但当 $N=1$ 时允许该位为 $0$）如果其十进制表示中不包含子串 $M$，则称为幸运数字。

请计算满足条件的幸运数字的个数。结果可能很大，对 $10000007$ 取模。

输入格式

第一行包含一个整数 $T$（$T\le 1000$），表示测试用例数。
接下来 $T$ 行，每行两个正整数 $N$ 和 $M$，其中 $N$ 是一个整数（$1\le N\le 100$），$M$ 是一个可能长达 $100$ 位的数字字符串。

输出格式

对于每个测试用例，输出一行一个整数，表示幸运数字的个数对 $10000007$ 取模的结果。

样例

输入

3
1 3
2 13
2 1

输出

9
89
72

样例解释

• $N=1$，$M=3$：一位数字有 $0\sim 9$，其中不含 3 的有 $9$ 个（$0,1,2,4,5,6,7,8,9$）。
• $N=2$，$M=13$：所有两位数为 $10\sim 99$，共 $90$ 个，其中包含 13 的只有 $13$ 这一个，故答案为 $89$。
• $N=2$，$M=1$：所有两位数中，十位不能为 $0$，且不含 1。十位可取 $2\sim 9$（$8$ 种），个位可取 $0,2\sim 9$（$9$ 种），共 $8\times 9=72$。

题目分析

本题的核心是计数长度为 $N$、首位非零且不包含给定模式串 $M$ 的数字串个数。由于 $N$ 很小（$N\le 100$），但 $M$ 可以很长（$100$ 位），因此不能枚举数字串，而是需要利用自动机状态转移进行动态规划。

考虑先放宽限制，允许前导零，计算长度为 $L$ 的任意数字串（允许前导零）中不含 $M$ 的个数，记为 $f(L)$。那么最终答案可以通过容斥得到：

• 当 $N=1$ 时，首位为零的数字就是 0，它不含任何正整数 $M$（因为 $M\ge 1$），因此答案就是 $f(1)$。
• 当 $N>1$ 时，首位为 $0$ 的串有 $10^{N-1}$ 个，但不含 $M$ 的个数等于 $f(N-1)$（因为 $M$ 不以 $0$ 开头，所以首位 $0$ 不会产生匹配影响）。因此实际答案为 $f(N)-f(N-1)$。

现在核心问题是计算 $f(L)$。我们可以在每个位置依次填入数字，并动态维护当前已匹配 $M$ 的前缀长度。这与字符串匹配中的 $\text{KMP}$ 自动机一致：状态表示当前已经匹配到 $M$ 的哪个前缀位置（$0$ 到 $|M|-1$）。当读入一个数字 $d$ 后，根据 $M$ 的失配函数转移到新状态。若新状态等于 $|M|$，则说明完整地出现了 $M$，该转移非法，否则合法。

由于 $N$ 只有 $100$，状态数最多为 $|M|\le 100$，转移数 $10$，因此可以直接递推。

解题思路

构建 $\text{KMP}$ 自动机

1. 对模式串 $M$ 计算前缀函数（$\text{next}$ 数组）。
2. 对于每个状态 $s$（$0\le s<|M|$）和每个数字 $d$（$0\sim 9$），模拟 $\text{KMP}$ 匹配过程，得到新状态 $s^{\prime }$。如果 $s^{\prime }=|M|$，表示匹配到了完整的 $M$，则这个转移不可用；否则可用。

动态规划计算 $f(L)$

定义 $\text{dp}[\ell ][s]$ 表示长度为 $\ell$、且当前匹配状态为 $s$ 的合法数字串个数（允许前导零）。初始 $\text{dp}[0][0]=1$。对于每个 $\ell$，枚举所有状态 $s$，然后尝试每个数字 $d$，若转移到的 $s^{\prime }$ 不是 $|M|$，则进行累加：

$$\text{dp}[\ell +1][s^{\prime }]+=\text{dp}[\ell ][s]$$

所有运算取模 $10000007$。最终：

$$f(L)=\sum _{s=0}^{|M|-1}\text{dp}[L][s]$$

由于 $N\le 100$，直接递推即可。

答案计算

• 若 $N=1$，答案为 $f(1)$。
• 否则，答案为 $(f(N)-f(N-1)+\text{MOD})\mathrm{mod}\text{MOD}$。

复杂度分析

• 对于每个测试用例，构建自动机需 $O(|M|\cdot 10)$，递推需 $O(N\cdot |M|\cdot 10)$。
• 总时间复杂度 $O(T\cdot (N\cdot |M|\cdot 10))$，在 $N,|M|\le 100$，$T\le 1000$ 时约为 $10^8$ 次运算，可接受。
• 空间复杂度 $O(|M|)$（存储转移表和 $\text{dp}$ 数组），若一次性构建转移表则为 $O(|M|\cdot 10)$。

代码实现

// Again Lucky Numbers
// UVa ID: 12040
// Verdict: Accepted
// Submission Date: 2026-06-24
// UVa Run Time: 0.030s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    const int MOD = 10000007;

    while (T--) {
        int N;
        string M;
        cin >> N >> M;
        int len = (int)M.size();

        // 构建 KMP 前缀函数
        vector<int> nextArr(len, 0);
        for (int i = 1; i < len; ++i) {
            int j = nextArr[i - 1];
            while (j > 0 && M[i] != M[j]) j = nextArr[j - 1];
            if (M[i] == M[j]) ++j;
            nextArr[i] = j;
        }

        // 构建自动机转移表 trans[state][digit] -> 新状态（可能等于 len，表示完全匹配）
        vector<vector<int>> trans(len, vector<int>(10, 0));
        for (int state = 0; state < len; ++state) {
            for (int digit = 0; digit < 10; ++digit) {
                char c = char('0' + digit);
                int ns = state;
                while (ns > 0 && M[ns] != c) ns = nextArr[ns - 1];
                if (M[ns] == c) ++ns;
                trans[state][digit] = ns; // 可能为 len
            }
        }

        // dp[length][state]：长度 length 的串，匹配状态为 state 的方案数（允许前导零）
        vector<vector<int>> dp(N + 1, vector<int>(len, 0));
        dp[0][0] = 1;
        vector<int> f(N + 1, 0);
        f[0] = 1; // 空串

        for (int length = 1; length <= N; ++length) {
            for (int state = 0; state < len; ++state) {
                int cur = dp[length - 1][state];
                if (cur == 0) continue;
                for (int digit = 0; digit < 10; ++digit) {
                    int ns = trans[state][digit];
                    if (ns < len) { // 未完全匹配 M，合法
                        dp[length][ns] = (dp[length][ns] + cur) % MOD;
                    }
                }
            }
            int sum = 0;
            for (int state = 0; state < len; ++state)
                sum = (sum + dp[length][state]) % MOD;
            f[length] = sum;
        }

        int ans;
        if (N == 1) ans = f[1];
        else ans = (f[N] - f[N - 1] + MOD) % MOD;

        cout << ans << '\n';
    }

    return 0;
}

总结

本题是一道典型的基于 $\text{KMP}$ 自动机的计数动态规划问题。关键技巧在于：

• 利用 $\text{KMP}$ 的失配指针构建自动机，将“不包含子串”的约束转化为状态转移的合法性判断。
• 采用容斥思想，先计算允许前导零的答案，再减去首位为零的情况，从而得到最终合法的 $N$ 位数个数。
• 由于 $N$ 和 $M$ 的长度都很小，直接二维 $\text{dp}$ 递推即可，无需矩阵快速幂等高级优化。

这种方法同样适用于其他类似的“不包含给定模式串”的数字计数问题，只需将模式串长度和 $N$ 的规模适当调整即可。处理大模数时注意取模操作，避免负数。