题解 P3311 【[SDOI2014]数数】

· · 题解

看到题解里面都是递推式dp，我来补一发记忆化搜索式的

主要思路

楼上已经讲得很清楚了。但为了过审为了加深理解，我还是来扯略讲一下。

看到题目里的多模式串匹配，显然可以想到AC自动机。再看到“计算不大于N的幸运数个数”，我们又可以发现这与数位dp有关。所以这题的算法正是：AC自动机+数位dp。

首先是AC自动机的基本操作，把集合S读进来，建立trie树，求出前缀指针。

然后，我们的问题就转化为了：在加上前缀指针的trie树上，找一条路径，不经过任何结尾节点，并且一路上经过的边所组成的数字不大于n，有多少种方案。

数位dp实现。

注意，一个节点是结尾节点，当且仅当这个点本身是结尾节点，或者其失配节点是结尾节点，或者其失配节点的失配节点是结尾节点，或者其失配节点的失配节点的。。。是结尾节点。我么可以用AC自动机求完前缀指针之后队列里面的残留数据来实现这一点。（具体见代码）

代码实现

AC自动机基本操作不再多讲，不会请自行补习。

这里重点讲一下数位dp。

我们设f[i][j]表示当前在处理第i位，当前在trie树的j这个节点，并且保证当前构成的数严格小于n，接下去有多少个符合要求的数字。

显然，在转移的时候，我们可以暴力枚举接下来选哪一个数。假设接下去选的数是k：

f[i][j]=\sum f[i+1][ch[j][k]](ch[j][k]$ 不是结尾节点$)

我们可以用记忆化搜索实现这一转移，代码如下：（我的数位dp中大小限制变量与别人是反过来的，阅读可能引起不适，请谅解）:

int dfs(int pos,int ch_pos,bool down,bool qiandaoling){
    if(pos>lenn) return !qiandaoling;//注意，请处理前导零问题
    if(down && ~f[pos][ch_pos]) return f[pos][ch_pos];//~f[pos][ch_pos]是f[pos][ch_pos]!=-1的装逼写法
    int end=down?9:sn[pos]-'0',res=0;//阅读可能引起不适，请谅解。
    for(int i=0;i<=end;i++){
        if(qiandaoling){//处理前导零问题
            if(!bo[ch[1][i]])
              res=(res+dfs(pos+1,ch[1][i],down || i!=end,qiandaoling && i==0))%p;//转移
        }
        else{
            if(!bo[ch[ch_pos][i]])
              res=(res+dfs(pos+1,ch[ch_pos][i],down || i!=end,false))%p;//转移
        }
    }
    if(down && !qiandaoling) f[pos][ch_pos]=res;//记忆化
    return res;
}

可以看到，我们刚刚处理了前导零问题。那么为什么要处理前导零呢？因为此题数据太坑爹。

我们可以看看这个数据：

10

1

01

如果你不处理前导零，那么你的输出将是9，而正确输出则是10.

因为在数位dp的时，我们在构成数字1的过程中一不小心包含了“01”这个子串（因为我们的n有两位，所以是从十位开始数位dp的）。而事实上，数字1是不包含"01"这个子串的，因为那个0是前导零。

所以我们要特判一下，忽略前导零。

真 · 代码

#include<bits/stdc++.h>
#define int long long
#define next fuck
using namespace std;
int const max_ch=1505;
int const p=1e9+7;
int m,lenn,tot=1,ch[max_ch][10],next[max_ch],que[max_ch],f[1205][max_ch];
bool bo[max_ch];
char sn[1205],s[1505];
inline void insert(char *s){
    int u=1,len=strlen(s);
    for(int i=0;i<len;i++){
        int c=s[i]-'0';
        if(!ch[u][c]) ch[u][c]=++tot;
        u=ch[u][c];
    }
    bo[u]=true;
}
inline void get_next(){
    for(int i=0;i<10;i++)
      ch[0][i]=1;
    next[1]=0,que[1]=1;
    for(int l=1,r=1;l<=r;l++){
        int u=que[l];
        for(int i=0;i<10;i++){
            if(!ch[u][i]) ch[u][i]=ch[next[u]][i];
            else{
                que[++r]=ch[u][i];
                next[ch[u][i]]=ch[next[u]][i];
            }
        }
    }
}
int dfs(int pos,int ch_pos,bool down,bool qiandaoling){
    if(pos>lenn) return !qiandaoling;
    if(down && ~f[pos][ch_pos]) return f[pos][ch_pos];
    int end=down?9:sn[pos]-'0',res=0;
    for(int i=0;i<=end;i++){
        if(qiandaoling){
            if(!bo[ch[1][i]])
              res=(res+dfs(pos+1,ch[1][i],down || i!=end,qiandaoling && i==0))%p;
        }
        else{
            if(!bo[ch[ch_pos][i]])
              res=(res+dfs(pos+1,ch[ch_pos][i],down || i!=end,false))%p;
        }
    }
    if(down && !qiandaoling) f[pos][ch_pos]=res;
    return res;
}
signed main(){
    scanf("%s",sn+1);
    lenn=strlen(sn+1);
    scanf("%lld",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s);
        insert(s);
    }
    get_next();
    for(int i=1;i<=tot;i++)
      bo[que[i]]=bo[que[i]] || bo[next[que[i]]];
    //利用队列里的残留数据
    memset(f,-1,sizeof(f));
    printf("%lld\n",dfs(1,1,false,true));
    return 0;
}