【Luogu】P3311数数（AC自动机上DP）

　　题目链接

　　蒟蒻今天终于学会了AC自动机，感觉很稳

　　（后一句愚人节快乐）

　　这题开一个f[i][j][k]表示有没有受到限制，正在枚举第j位，来到了AC自动机的第k个节点

　　的方案数

　　随后可以刷表更新

　　注意如果是在枚举第一位的话注意前导0

　　

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<queue>

#define maxl 2000

#define maxu 10

#define mod 1000000007

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

inline int count(int i){    return i-'';    }

int tree[maxl*maxu][maxu];

int fail[maxl*maxu];

int val[maxl*maxu];

int tot;

char c[maxl];

char s[maxl];

long long f[][maxl][maxl];

bool vis[maxl];

void update(){

    int n=strlen(c+);    int now=;

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

        if(tree[now][count(c[i])]==)    tree[now][count(c[i])]=++tot;

        now=tree[now][count(c[i])];

    }

    val[now]++;

    return;

}

void makefail(){

    queue<int>q;

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

        if(tree[][i])    q.push(tree[][i]);

    while(!q.empty()){

        int from=q.front();q.pop();

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

            if(tree[from][i]==){

                tree[from][i]=tree[fail[from]][i];

                continue;

            }

            fail[tree[from][i]]=tree[fail[from]][i];

            val[tree[from][i]]|=val[tree[fail[from]][i]];

            q.push(tree[from][i]);

        }

    }

    return;

}

inline void add(long long &a,int b){

    a=(a+b)%mod;

}

int main(){

    scanf("%s",s+);int n=strlen(s+);

    int m=read();

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

        scanf("%s",c+);

        update();

    }

    long long ans=;

    makefail();

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

        for(int j=;j<=tot;++j){

            if(f[][i][j]){

                int now=s[i+]-'';

                for(int k=;k<now;++k){

                    int nxt=tree[j][k];

                    if(val[nxt]==)    add(f[][i+][nxt],f[][i][j]);

                }

                int nxt=tree[j][now];

                if(val[nxt]==)    add(f[][i+][nxt],f[][i][j]);

            }

            if(f[][i][j]){

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

                    int nxt=tree[j][k];

                    if(val[nxt]==)    add(f[][i+][nxt],f[][i][j]);

                }

            }

            if(j==){

                if(i==){

                    int now=s[i+]-'';

                    for(int k=;k<now;++k){

                        int nxt=tree[j][k];

                        if(val[nxt]==)    add(f[][i+][nxt],);

                    }

                    int nxt=tree[j][now];

                    if(val[nxt]==)    add(f[][i+][nxt],);

                }

                else{

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

                        int nxt=tree[j][k];

                        if(val[nxt]==)    add(f[][i+][nxt],);

                    }

                }

            }

        }

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

        add(ans,f[][n][i]);

        add(ans,f[][n][i]);

    }

    ans=(ans+mod)%mod;

    printf("%lld\n",ans);

}