[SDOI2014]数数（AC自动机，动态规划）

· · 题解

[SDOI2014]数数（AC自动机，动态规划）

写题解前先泄愤...本来觉得应该像数位dp一样搞一个当前是否还是前导零的一维，由于当时特别困导致调不下去就盯着代码发呆，浪费时间浪费生命[快哭了]

想在这里请诸位查一下我的以前那份错误的代码qwq，也算是为自己留存一下疑惑，以后想得起来继续查。code

题目叙述

给你一个由数字组成的字符串，要求这个字符串的子串中不能出现某些字符串，并且这个字符串组成的数不能比某个给定的数大。

题解

设dp_{i,j,0/1}表示前i位，现在匹配到AC自动机上的第j个点，现在分出来/没分出大小一共有多少种。

转移：

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxLen = 1205, maxNode = 1505, mod = 1e9 + 7;
int ch[maxNode][10], dp[maxLen][maxNode][2], fail[maxNode], tot = 1, nbLim;
bool tag[maxNode];
char big[maxLen], lim[maxLen];
queue<int> Q;
//dp[i][0/1][0/1]表示前 i位，有没有分出大小，当前还是不是前导零 
void Insert(char *str) {
    int len = strlen(str + 1), now = 1;
    for (int pos = 1; pos <= len; ++pos) {
        if (!ch[now][str[pos] - '0'])
            ch[now][str[pos] - '0'] = ++tot;
        now = ch[now][str[pos] - '0'];
    }
    tag[now] = 1;
}
void GetFail() {
    fail[1] = 1;
    for (int son = 0; son < 10; ++son) {
        if (ch[1][son]) {
            fail[ch[1][son]] = 1;
            Q.push(ch[1][son]);
        } else
            ch[1][son] = 1;
    }
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        for (int son = 0; son < 10; ++son) {
            if (ch[now][son]) {
                Q.push(ch[now][son]);
                fail[ch[now][son]] = ch[fail[now]][son];
            } else
                ch[now][son] = ch[fail[now]][son];
        }
    }
}
void Add(int &x, int y) {
    x += y, (x > mod) ? x -= mod : x = x;
}
void Minus(int &x, int y) {
    x -= y, (x < 0) ? x += mod : x = x; 
}
void Check() {
    for (int i = 1; i <= tot; ++i) {
        printf("node : %d fail : %d\n", i, fail[i]);
        for (int son = 0; son < 10; ++son)
            if (ch[i][son])
                printf("    ch : %d son : %d\n", son, ch[i][son]);
    }
}
int main() {
    scanf("%s%d", big + 1, &nbLim);
    for (int i = 1; i <= nbLim; ++i) {
        scanf("%s", lim + 1);
        Insert(lim);
    }
    GetFail();
    int bigLen = strlen(big + 1);
    dp[0][1][0] = 1;
    ch[1][0] = 1;
    for (int len = 0; len < bigLen; ++len) {
        for (int node = 1; node <= tot; ++node) {
            if (tag[node])
                continue ;
            for (int son = 0; son < 10; ++son) {
                if (tag[ch[node][son]])
                    continue ;
                Add(dp[len + 1][ch[node][son]][0], dp[len][node][0] * (son == (big[len + 1] - '0')));
                Add(dp[len + 1][ch[node][son]][1], dp[len][node][1]);
                Add(dp[len + 1][ch[node][son]][1], dp[len][node][0] * (son < (big[len + 1] - '0')));
            }
        }
    }
    int ans = 0;
    for (int node = 1; node <= tot; ++node)
        Add(ans, dp[bigLen][node][0]), Add(ans, dp[bigLen][node][1]);
    Minus(ans, 1);
    printf("%d\n", ans);
    return 0;
}

知识点