题目地址：洛谷：【P3311】[SDOI2014]数数 – 洛谷、BZOJ：Problem 3530. — [Sdoi2014]数数

题目描述

我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。 给定N和S，计算不大于N的幸运数个数。

输入输出格式

输入格式：
输入的第一行包含整数N。 接下来一行一个整数M，表示S中元素的数量。 接下来M行，每行一个数字串，表示S中的一个元素。

输出格式：
输出一行一个整数，表示答案模10^9+7的值。

输入输出样例

输入样例#1：

20
3
2
3
14

输出样例#1：

14

说明

下表中l表示N的长度，L表示S中所有串长度之和。
1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500

题解

参考资料：题解 P3311 【[SDOI2014]数数】 – 东吴四杰 的博客 – 洛谷博客
最开始想的是用一个数位DP套AC自动机做，然后发觉复杂度不对，然后才发现是在AC自动机上跑DP。好久没打AC自动机还给打错了，VS又坏掉了，又有好几个地方打错了，简直是flag成片。
用dp[i][j]表示枚举数字到第i位，且在AC自动机上跑到j这个点的方案数。由于我们还要考虑不大于N的限制，还得往状态里加一维表示当前位是否受到限制。
转移就很简单了，枚举下一个数字，然后把当前位的方案加到下个数字中。如果当前位仍然受限，那么就枚举当前位直到限制，分别处理一下下一位是否受限。
DP的时候需要关注一下初值。枚举时如果当前节点是AC自动机的根0，那么需要对下一位设置初值。当下一位是枚举的第一位时，要考虑N的限制，令dp[1][1][p < lim]=1，dp[0][1][p == lim]=1，否则，要设置前几位全0的情况，dp[1][i][p]=1。
建立AC自动机的时候，算fail要把单词结尾标记传递下来，避免出现某个后缀是另外一个单词的情况（但是好像数据不够强没有这种情况）。
复杂度O(10n^2)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

const int MAXN = 2005, MO = 1e9 + 7;

int ch[MAXN][10], tot;
bool wrd[MAXN];

inline void insert(char *str) {
    int p = 0;
    for(int i = 1; str[i]; i++) {
        int t = str[i] - '0';
        if(!ch[p][t]) ch[p][t] = ++tot;
        p = ch[p][t];
    }
    wrd[p] = true;
}

int fail[MAXN];
std::queue<int> que;

inline void calfail() {
    for(int i = 0; i <= 9; i++) {
        if(ch[0][i]) que.push(ch[0][i]);
    }
    while(!que.empty()) {
        int p = que.front(); que.pop();
        for(int i = 0; i <= 9; i++) {
            if(ch[p][i]) {
                fail[ch[p][i]] = ch[fail[p]][i];
                wrd[ch[p][i]] |= wrd[ch[fail[p]][i]];
                que.push(ch[p][i]);
            } else {
                ch[p][i] = ch[fail[p]][i];
            }
        }
    }
}

int n, m;
char num[MAXN], tmp[MAXN];
LL dp[2][MAXN][MAXN];

int main() {
    scanf("%s%d", num + 1, &m);
    n = strlen(num + 1);
    for(int i = 1; i <= m; i++) {
        scanf("%s", tmp + 1);
        insert(tmp);
    }
    calfail();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= tot; j++) {
            if(dp[0][i][j]) {
                for(int k = 0; k < num[i + 1] - '0'; k++) {
                    int p = ch[j][k];
                    if(!wrd[p]) dp[1][i + 1][p] = (dp[1][i + 1][p] + dp[0][i][j]) % MO;
                }
                int p = ch[j][num[i + 1] - '0'];
                if(!wrd[p]) dp[0][i + 1][p] = (dp[0][i + 1][p] + dp[0][i][j]) % MO;
            }
            if(dp[1][i][j]) {
                for(int k = 0; k <= 9; k++) {
                    int p = ch[j][k];
                    if(!wrd[p]) dp[1][i + 1][p] = (dp[1][i + 1][p] + dp[1][i][j]) % MO;
                }
            }
            if(j == 0) {
                if(i == 0) {
                    for(int k = 1; k < num[i + 1] - '0'; k++) {
                        int p = ch[j][k];
                        if(!wrd[p]) dp[1][i + 1][p]++;
                    }
                    int p = ch[j][num[i + 1] - '0'];
                    if(!wrd[p]) dp[0][i + 1][p]++;
                } else {
                    for(int k = 1; k <= 9; k++) {
                        int p = ch[j][k];
                        if(!wrd[p]) dp[1][i + 1][p]++;
                    }
                }
            }
        }
    }
    LL ans = 0;
    for(int i = 0; i <= tot; i++) {
        ans = (ans + dp[0][n][i]) % MO;
        ans = (ans + dp[1][n][i]) % MO;
    }
    printf("%lld", ans);
    return 0;
}