🔍 题目核心与约束分析

题目要求统计所有满足以下条件的幸运数：

1. 不大于给定的正整数 $N$（以字符串形式给出，长度 $l \leq 1200$）。
2. 其十进制表示中不包含数字串集合 $S$（$M \leq 100$，总长度 $L \leq 1500$）中的任何元素作为子串。这些数字串可能包含前导零。

关键点：

• $N$ 很大，必须进行数位处理。
• 需要高效进行多模式串匹配，并处理模式串之间的包含关系。
• 数字串可能有前导0，这会影响匹配逻辑，需要特别注意。

💡 核心思路：AC自动机 + 数位DP

此问题的标准解法是结合 AC自动机（Aho-Corasick Automaton） 和 数位DP。

🔹 第一步：构建AC自动机

AC自动机（Trie图）能帮助我们高效地进行多模式串匹配。

1. 插入模式串：将 $S$ 中的所有数字串插入到一棵 Trie 树 中。
2. 构建失败指针：为Trie树中每个节点构建失败指针。这样，在匹配过程中若当前字符失配，能快速跳转到最长的可能后缀匹配位置。
3. 标记非法节点：在构建好AC自动机后，需要标记出所有“非法”节点。如果一个节点代表的串本身是某个禁止串的结尾，或者其失败指针指向的节点是非法节点，那么该节点也是非法的。这确保了只要匹配路径经过任意禁止串，就会被标记。

🔹 第二步：数位动态规划

在AC自动机上进行数位DP，统计合法的数字数量。

1. 状态设计： 常用的状态是 dp[pos][node][limit][lead]：

   • pos：当前处理到 $N$ 的第几位（从高位到低位）。
   • node：当前在AC自动机上的节点编号。
   • limit：布尔值，表示之前的数位是否已紧贴 $N$ 的对应位（决定当前数位选择范围）。
   • lead：布尔值，表示当前是否处于前导零状态。

2. 处理前导零：这是本题的一个关键点和易错点。

   • 当处于前导零状态时，数字实际上还没有真正开始。此时，如果选择数字 0，应该保持在AC自动机的根节点（或根据实现保持在特定节点），不能沿着代表 0 的边向下走。因为前导零不应参与禁止串的匹配。
   • 只有当遇到非零数字，或者已经不在前导零状态时，才在AC自动机上正常转移。

3. 状态转移：

   • 枚举当前位可以选择的数字 $d$（从 0 到 limit 决定的当前上限）。
   • 根据 lead 和当前选择的数字 $d$，判断下一步在AC自动机上的节点 $next\\_node$：
     • 如果当前处于前导零且 $d = 0$，则 $next\\_node$ 保持为根节点（或特定节点）。
     • 否则，从当前节点 $node$ 沿着边 $d$ 走到 $next\\_node$。
   • 如果 $next\\_node$ 是非法节点，说明此路径包含禁止串，跳过。
   • 否则，递归计算后续数位的方案数，并累加到状态中。

4. 记忆化：在 limit 为 false（未紧贴上限）且 lead 为 false（不处于前导零）时，可以对 dp[pos][node] 进行记忆化，避免重复计算。

5. 最终答案：通常是从最高位开始，在根节点，处于上限状态和前导零状态开始进行DFS的返回值。注意，结果可能需要减去代表数字0的方案（如果它被统计在内），因为题目要求的是正整数。

🧮 算法实现与细节

代码框架（仅供参考）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1505; // AC自动机节点数，约为总串长

int dp[1205][MAXN]; // DP数组，第一维是位置，第二维是AC自动机节点
int ch[MAXN][10], fail[MAXN], bo[MAXN], tot = 1; // AC自动机相关数组，bo标记非法节点
char N_str[1205]; // 存储大数N
int lenN; // N的长度

// 插入一个模式串s
void insert(char *s) {
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = s[i] - '0';
        if (!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
    bo[u] = 1; // 标记原始非法节点
}

// 构建AC自动机的失败指针
void build_fail() {
    queue<int> q;
    for (int i = 0; i < 10; i++) ch[0][i] = 1; // 0号节点作为虚拟根
    q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 10; i++) {
            if (!ch[u][i]) ch[u][i] = ch[fail[u]][i];
            else {
                fail[ch[u][i]] = ch[fail[u]][i];
                // 传递非法标记：如果fail指针指向的节点是非法节点，那么当前节点也是非法的
                bo[ch[u][i]] |= bo[fail[ch[u][i]]];
                q.push(ch[u][i]);
            }
        }
    }
}

// 数位DP记忆化搜索
// pos: 当前处理位置, node: AC自动机节点, limit: 是否紧贴上界, lead: 是否处于前导零
int dfs(int pos, int node, bool limit, bool lead) {
    if (pos == lenN) return !lead; // 处理完所有数位，如果不在前导零状态（即是一个有效的数）则返回1
    if (!limit && !lead && dp[pos][node] != -1) return dp[pos][node]; // 记忆化
    int res = 0;
    int up = limit ? (N_str[pos] - '0') : 9;
    for (int d = 0; d <= up; d++) {
        int nxt_node;
        if (lead && d == 0) {
            // 保持前导零状态，节点保持在根节点（或特定节点，具体看实现）
            nxt_node = node; // 通常是根节点，这里需要根据你的AC自动机初始化情况调整
        } else {
            nxt_node = ch[node][d];
        }
        if (bo[nxt_node]) continue; // 跳过非法节点
        res = (res + dfs(pos + 1, nxt_node, limit && (d == up), lead && (d == 0))) % MOD;
    }
    if (!limit && !lead) dp[pos][node] = res;
    return res;
}

int main() {
    // 读取输入
    scanf("%s", N_str);
    lenN = strlen(N_str);
    int M;
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        char s[1505];
        scanf("%s", s);
        insert(s);
    }
    build_fail();
    memset(dp, -1, sizeof(dp));
    // 初始状态：位置0, 节点1（根节点）, 紧贴上界, 处于前导零状态
    printf("%d\n", dfs(0, 1, true, true));
    return 0;
}

⚠️ 注意事项

1. 根节点处理：AC自动机的根节点通常设为1，并设置一个虚拟节点0作为所有节点的最终失败指向，具体实现需注意节点编号的初始化和边界处理。
2. 非法节点标记传递：在构建失败指针时，务必进行非法节点的标记传递（bo[ch[u][i]] |= bo[fail[ch[u][i]]];），确保包含禁止串后缀的节点也被标记。
3. 前导零与根节点：前导零状态下，选择数字0时保持在根节点（或特定节点）是正确处理前导零不参与匹配的关键。
4. 模运算：记得在每次加法后取模。
5. 大数N的表示：$N$ 以字符串形式读入，便于按位处理。

💎 总结

这道题的核心在于：

1. AC自动机：高效处理多模式串匹配和非法状态传递。
2. 数位DP：按位决策，统计合法数字数量。
3. 前导零处理：区分前导零和真正的数字起始，避免错误匹配。