看到多模式匹配,我们考虑先对所有模式串建立AC自动机。
然后发现这道题和P4052 文本生成器(题解)挺像的,后者让求包含至少一个模式串的个数,这道题让求一个也不包含的个数,这个就是一个用不用\(26^m\)去减的问题,很好处理。但这道题还多了一个条件,“幸运数”必须\(\le n\),而\(n\)足足有\(1200\)位,所以很自然地想到数位dp。
实际上,P4052也可以用数位dp来解决,只不过填写没有大小限制,每个节点都可以填A
~Z
。换到这道题上也一样,只不过记忆化的前提是“当前非前导\(0\)”而且“填写当前位无限制”。
下文中的“答案”均表示“不可读的字符串个数”。
用\(f[pos][p]\)来表示“主串第\(pos\)个字符对应自动机上节点\(p\)”的答案。
数位dp提供\(4\)个参数:
int
\(pos\):当前在主串的哪一位(从最高位开始,以\(pos=0\)为结束条件)。int
\(p\):\(当前pos\)对应自动机上哪个节点。bool
\(limit\):填写是否受限(数位dp标配)。bool
\(zero\):是否是前导\(0\)(数位dp标配)。
用\(f\)记忆化即可。
int dfs(int pos,int p,bool limit,bool zero){
if(en[p]) return 0;//如果遇到字符串结尾,则答案一定为0
if(!pos) return !zero;//限定正整数
if(!limit&&!zero&&~f[pos][p]) return f[pos][p];
int rig=limit?a[pos]:9;
int ans=0;
for(int i=0;i<=rig;i++){
int tzero=zero&&!i;
ans=(ans+dfs(pos-1,tzero?0:tr[p][i],limit&&i==rig,tzero))%mod;
}
if(!limit&&!zero) f[pos][p]=ans;
return ans;
}
时间复杂度\(O(\log_{10}n\times \sum|s|\times |\Sigma|)\)。
点击查看代码
#include<bits/stdc++.h>
#define mod 1000000007
#define N 1510//节点数(模式串总长)
#define M 1210//主串长度
#define C 10//字符集大小
using namespace std;
int n,m,tr[N][C],fail[N],cnt;
int q[N],head,tail,f[M][N],a[M];
bool en[N];
string s,t;
void ins(string s){
int p=0;
for(char i:s){
int c=i-'0';
if(!tr[p][c]) tr[p][c]=++cnt;
p=tr[p][c];
}
en[p]=1;
}
void get_fail(){
head=0,tail=-1;
for(int i=0;i<C;i++) if(tr[0][i]) q[++tail]=tr[0][i];
while(head<=tail){
int u=q[head++];
for(int i=0;i<C;i++){
if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q[++tail]=tr[u][i],
en[tr[u][i]]|=en[fail[tr[u][i]]];
else tr[u][i]=tr[fail[u]][i];
}
}
}
int dfs(int pos,int p,bool limit,bool zero){
if(en[p]) return 0;
if(!pos) return !zero;
if(!limit&&!zero&&~f[pos][p]) return f[pos][p];
int rig=limit?a[pos]:9;
int ans=0;
for(int i=0;i<=rig;i++){
int tzero=zero&&!i;
ans=(ans+dfs(pos-1,tzero?0:tr[p][i],limit&&i==rig,tzero))%mod;
}
if(!limit&&!zero) f[pos][p]=ans;
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>s>>m;
for(int i=1;i<=m;i++){
cin>>t;
ins(t);
}
get_fail();
memset(f,-1,sizeof f);
n=s.size();
for(int i=0;i<n;i++) a[n-i]=s[i]-'0';
cout<<dfs(n,0,1,1)<<"\n";
return 0;
}
一个问题
好像发现了什么……
题解区有些不用dfs,用数组线性递推答案的写法,可以把\(f\)的第一维滚掉,因为第一维是最外层循环枚举的,且\(f[i]\)只和\(f[i-1]\)有关;然而dfs写法应该是滚不掉的,因为一次跑到底,那么每个\(f[i]\)都存在有用的值,所以不能滚。
解决数位dp一般首选dfs,但上面的空间问题,难道是dfs写法的一个弊端吗?能否解决这个问题?
想到了bfs之类的解决方案,但是还没梳理出头绪,网上也貌似完全没有提到bfs实现的数位dp。
如果大家有任何想法请发在评论区,谢谢!
标签:int,题解,pos,dfs,SDOI2014,P3311,bool,dp,数位 From: https://www.cnblogs.com/Sinktank/p/18369775