题目内容

给定 $m$ 个可爱数字串，它们仅由 $0$ ~ $9$ 这九个数字字符构成，且可能包含前导 $0$。

你需要求解，在区间 $[1,n]$ 中，有多少个整数满足，可爱度恰好为 $1$。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。在这里，一个整数的可爱度定义为：

解题思路

要在超长上界 $n$ 下计数，不能枚举。我们结合Aho–Corasick 自动机和数位 DP（Digit DP）来做：

1. 构建 Aho–Corasick 自动机

1. 插入模式串：将所有 $m$ 个可爱数字串插入字典树，每个结尾节点记录“权重”——该串出现的次数（如果有相同串插入多次，权重大于1）。
2. 构建 fail 指针：BFS 建立 fail 链，并在每个节点汇总其 fail 链上所有模式串的权重，这样在匹配过程中，只要落到某节点，就知道以该位置为结尾的新匹配数。

构建复杂度：