题解 P3311 【[SDOI2014]数数】
ωαηg
2019-05-04 08:29:54
看到题解里面都是递推式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中大小限制变量与别人是反过来的，阅读可能引起不适，请谅解）:
```cpp
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是前导零。
所以我们要特判一下，忽略前导零。
----
### 真 · 代码
```cpp
#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;
}
```