P3311题解

· · 题解

这是一篇记忆化搜索题解

主要谈谈这个题的特判，当时卡了我好一会

可以看出，这道题应该是数位 DP + AC 自动机

有关 AC 自动机的内容这里不再补充

非常形式化地，数位DP的状态设计：

f_{pos,st,flg,zero}

pos :当前要处理第几位

st :用于储存前面的状态，可能是上一个数，也可能是前缀和，gcd 等等，这个题应该是前面在AC自动机上的位置

flg :当前位是否被所求数限制，比如要求的是 114514，而此时你求了前三位，现在要处理 114---，这样你第四位就只能到 5 ，但如果你第三位是 3 或者更小的，你第四位是多少就无所谓了

zero ：前面是否有前导零

然后就可以愉快地开始记忆化搜索了，具体思路也不难，搜到了某一位，接着向下搜，就把新的一位在自动机上面跳一下，如果不是某个模式串的结尾就可以继续 DFS

跳完后到了最后一位只要不是全是 0 都是 1 ，因为前面各位都已经确定了

或者说解释一下 DFS 的含义，返回小于等于所求的数，所有尚未确定的可能情况的幸运数个数，因为刚开始全都不确定就会是最后的答案，到了最后全都确定了就会是 1

特判

注意这里模式串是可能有前导零的，而幸运数不允许有前导零，这可能会发生什么情况，比如你要求 114514，你处理到了第三位，是个 0023-- ，这时你的模式串有一个 0023，那么这种情况就会被判断为不合法，但实际上里应该被判断为 23-- ，不能看前导零，应该是一种合法的情况。所以总结一下，要特判的就是模式串有前导零且当前数也有前导零的情况

这里加一句特判就可以

if(zero)st=0;

然后就可以贴代码了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define rint register int
#define lint long long
#define ldouble long double
using namespace std;
inline int read(){
    char c;int res=0,f=1;
    while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return f*res;
}
const int M=1e2+5,S=15e2+5;
const lint mod=1e9+7;
string n,s[M];
int m,len;
int nxt[S][10],fil[S],cnt=0;
bool tail[S];
inline void inst(string str){//构建字典树 
    int i,j,siz=str.size(); 
    for(i=0,j=0;i<siz;++i){
        int tmp=str[i]-'0';
        if(!nxt[j][tmp])
            nxt[j][tmp]=++cnt;
        j=nxt[j][tmp];
    }
    tail[j]=true;
}
inline void gfil(){//获得fail指针 
    queue<int> que;
    for(rint i=0;i<10;++i)
        if(nxt[0][i]){
            fil[nxt[0][i]]=0;
            que.push(nxt[0][i]);
        }
    while(!que.empty()){
        int u=que.front();
        que.pop();
        tail[u]|=tail[fil[u]];
        for(rint i=0;i<10;++i){
            if(nxt[u][i]){
                fil[nxt[u][i]]=nxt[fil[u]][i];
                que.push(nxt[u][i]);
            }
            else nxt[u][i]=nxt[fil[u]][i];
        }
    }
}
lint f[S][S][2][2]={0};
lint DFS(int x,int st,bool flg,bool zero){//形式化的记忆化搜索 
    if(x==len)return !zero;//如果不是全是0那么只有一种确定的情况 
    if(f[x][st][flg][zero])return f[x][st][flg][zero];
    int e=(flg?n[x]-'0':9);//看看之前的位是否达到上限 
    lint res=0;
    if(zero)st=0;
    for(rint i=0;i<=e;++i){
        if(!tail[nxt[st][i]]){
            res+=DFS(x+1,nxt[st][i],flg&&i==e,zero&&i==0);
            /*
            前面顶了上限这位还顶上限那么下一位就会被限制
            前面有前导零这一位还是0意味着还有前导零 
            */ 
            res%=mod;
        }
    }
    return f[x][st][flg][zero]=res;
}
int main(){
    cin>>n;
    len=n.size();
    m=read();
    for(rint i=1;i<=m;++i){
        cin>>s[i];
        inst(s[i]);
    }
    gfil();
    printf("%lld\n",DFS(0,0,true,true));
    return 0;
}