题目链接：
题目分析
明显是 AC自动机+DP，外加数位统计。
WZY 神犇出的良心省选题，然而去年我太弱..比现在还要弱得多..
其实现在做这道题，我自己也没想出完整解法..
就想出了个 O(l^3) 的做法：
完全按照数位统计的思想来，先统计长度不足 len 的数字的合法种类数，这个枚举开头，然后 AC 自动机 DP 一下，用 f[i][j] 表示到了第 i 位，在第 j 个节点上的合法数字个数。这样是 O(L^2)。
然后长度等于 n 的部分，就按照数位统计，一位位向后推，然后每次 O(L^2) DP 求，这样总的复杂度是 O(L^3)。
注意不能走包含模式串的节点，首先 Trie 中模式串的节点肯定不能走，其次，如果沿着一个节点的 Fail 链一直向上走，只要链上有一个节点是不能走的，那么这个节点也就不能走了。
所以需要从每个的节点开始，逆着 Fail 的边 DFS 一下，如果当前状态下将经过的点全都 Ban 掉。但是数据好像比较弱，不加这个也是不会出问题的。
但是这样会弄错一种情况：比如有 123， 2 这两个串，然后它就沿着 -> 1 -> 2 一直向后匹配，没有匹配成功 123 ，但是其实已经包含了 2 这个串。
这样的复杂度只有70分。
正解的复杂度是 O(L^2) 的：对于长度不足 len 的数字，还是直接求，O(L^2)。
对于长度等于 len 的数字，我们就直接用一个 O(L^2) 的 DP 求出来，我们把状态增加一维， g[i][j][k] ，前两位是第 i 位，走到第 j 个节点，k 是一个 [0/1] 变量，表示这个状态是否是沿着 n 的每一位走过来。
这样我们就知道了，如果当前状态是依照 n 的每一位走过来，那么下一步就只能转移 [0, n[i+1]] 这些数字。否则可以转移所有的数字。这样就求出了小于等于 n 的所有合法数字。
总的复杂度是 O(L^2) 。
AC自动机+DP的一般做法：f[i][j] 表示走了 i 步，走到了第 j 个节点，有时还需要加第 3 维或更多。
然后 DP 的时候就是 枚举 i ，枚举 j，枚举转移到下一步的字符。
代码
#include#include #include #include #include #include #include using namespace std;const int MaxL = 1500 + 5, MaxNode = 15000 + 5, Mod = 1000000007;int len, l, m, Index, Ans;int f[MaxL][MaxNode], g[MaxL][MaxNode][2];char S[MaxL], Ns[MaxL];struct Trie{ int x, Idx; bool Ban; Trie *Fail, *Child[10];} TA[MaxNode], *P = TA, *Root, *Zero;Trie* NewNode(int Num = 0){ ++P; P -> x = Num; P -> Idx = ++Index; P -> Fail = NULL; P -> Ban = false; memset(P -> Child, 0, sizeof(P -> Child)); return P;}void Insert(char *S, int l){ int t; Trie *Now = Root; for (int i = 1; i <= l; ++i) { t = S[i] - '0'; if (Now -> Child[t] == NULL) Now -> Child[t] = NewNode(t); Now = Now -> Child[t]; } Now -> Ban = true;}struct Edge{ int v; Edge *Next;} E[MaxNode], *PE = E, *Point[MaxNode];inline void AddEdge(int x, int y){ ++PE; PE -> v = y; PE -> Next = Point[x]; Point[x] = PE;}bool Visit[MaxNode];void DFS(int x, bool f){ Visit[x] = true; TA[x].Ban = (TA[x].Ban) || f; for (Edge *j = Point[x]; j; j = j -> Next) DFS(j -> v, TA[x].Ban);}queue Q;void Build_Fail(){ while (!Q.empty()) Q.pop(); Q.push(Root); Trie *Now; while (!Q.empty()) { Now = Q.front(); Q.pop(); AddEdge(Now -> Fail -> Idx, Now -> Idx); for (int i = 0; i <= 9; ++i) { if (Now -> Child[i] == NULL) Now -> Child[i] = Now -> Fail -> Child[i]; else { Now -> Child[i] -> Fail = Now -> Fail -> Child[i]; Q.push(Now -> Child[i]); } } } for (int i = 1; i <= Index; ++i) if (!Visit[i]) DFS(i, TA[i].Ban);}void Usual_Disco(){ memset(f, 0, sizeof(f)); for (int i = 1; i <= 9; ++i) if (Root -> Child[i] -> Ban == false) ++f[1][Root -> Child[i] -> Idx]; for (int i = 1; i < len; ++i) for (int j = 1; j <= Index; ++j) { if (TA[j].Ban) continue; Ans = (Ans + f[i][j]) % Mod; for (int t = 0; t <= 9; ++t) if (!TA[j].Child[t] -> Ban) { f[i + 1][TA[j].Child[t] -> Idx] += f[i][j]; f[i + 1][TA[j].Child[t] -> Idx] %= Mod; } } memset(g, 0, sizeof(g)); for (int i = 1; i < Ns[1] - '0'; ++i) if (Root -> Child[i] -> Ban == false) ++g[1][Root -> Child[i] -> Idx][0]; if (Root -> Child[Ns[1] - '0'] -> Ban == false) ++g[1][Root -> Child[Ns[1] - '0'] -> Idx][1]; for (int i = 1; i <= len; ++i) for (int j = 1; j <= Index; ++j) { if (TA[j].Ban) continue; if (i == len) { Ans = (Ans + g[i][j][0]) % Mod; Ans = (Ans + g[i][j][1]) % Mod; continue; } for (int t = 0; t <= 9; ++t) if (!TA[j].Child[t] -> Ban) { g[i + 1][TA[j].Child[t] -> Idx][0] += g[i][j][0]; g[i + 1][TA[j].Child[t] -> Idx][0] %= Mod; } for (int t = 0; t < Ns[i + 1] - '0'; ++t) if (!TA[j].Child[t] -> Ban) { g[i + 1][TA[j].Child[t] -> Idx][0] += g[i][j][1]; g[i + 1][TA[j].Child[t] -> Idx][0] %= Mod; } if (!TA[j].Child[Ns[i + 1] - '0'] -> Ban) { g[i + 1][TA[j].Child[Ns[i + 1] - '0'] -> Idx][1] += g[i][j][1]; g[i + 1][TA[j].Child[Ns[i + 1] - '0'] -> Idx][1] %= Mod; } }}int main(){ scanf("%s", Ns + 1); len = strlen(Ns + 1); scanf("%d", &m); Root = NewNode(); Zero = NewNode(); Root -> Fail = Zero; for (int i = 0; i <= 9; ++i) Zero -> Child[i] = Root; for (int i = 1; i <= m; ++i) { scanf("%s", S + 1); l = strlen(S + 1); Insert(S, l); } Build_Fail(); Usual_Disco(); Ans %= Mod; cout << Ans << endl; return 0;}