3530: [Sdoi2014]数数

链接

分析：

　　对给定的串建立AC自动机，然后数位dp。数位dp的过程中，记录当前在AC自动机的哪个点上，保证不能走到出现了给定串的点。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = 1e9 + ;

int ch[N][], q[N], fail[N], last[N], val[N], dp[N][N], Index;

char s[N], t[N];

void Insert(char *s) {

    int len = strlen(s), u = ;

    for (int i = ; i < len; ++i) {

        int c = s[i] - '';

        if (!ch[u][c]) ch[u][c] = ++Index;

        u = ch[u][c];

    }

    val[u] = ;

}

void bfs() {

    int L = , R = ;

    for (int i = ; i < ; ++i)

        if (ch[][i]) q[++R] = ch[][i];

    while (L <= R) {

        int u = q[L ++];

        for (int c = ; c < ; ++c) {

            int v = ch[u][c];

            if (!v) ch[u][c] = ch[fail[u]][c];

            else fail[v] = ch[fail[u]][c], last[v] = val[fail[v]] ? fail[v] : last[fail[v]], q[++R] = v;

        }

    }

}

int dfs(int pos,int now,bool lim,bool fir) { // 从高位数第pos位，在AC自动机上的位置，是否有小于n的限制，是否有前导0的限制

    if (pos == ) return ;

    if (!lim && !fir && dp[pos][now] != -) return dp[pos][now];

    int res = , u = lim ? (s[pos] - '') : ;

    if (fir) res = (res + dfs(pos - , , lim &&  == u, )) % mod; // 如果当前依然没有出现第一个正整数作为开始，那么继续从0号点开始走，不能是ch[0][0]!!!

    for (int i = fir; i <= u; ++i) {

        int v = ch[now][i];

        if (val[v] || last[v]) continue; // last表示从当前点沿着fail指针跳的过程中，第一个是给定串的点

        res = (res + dfs(pos - , v, lim && i == u , )) % mod;

    }

    if (!lim && !fir) dp[pos][now] = res;

    return res;

}

int main() {

    scanf("%s", s + );

    int n = strlen(s + );

    reverse(s + , s + n + );

    int m = read();

    for (int i = ; i <= m; ++i) {

        scanf("%s", t);

        Insert(t);

    }

    bfs();

    memset(dp, -, sizeof(dp));

    cout << (dfs(n, , , ) -  + mod) % mod;

    return ;

}