被慎老师教育数位(dp)怎么写了
看来我数位(dp)的写法太落后了
这道题很显然就是一个(AC)自动机上的数位(dp)，按照套路
我们可以设计(dp[i][j][0/1])表示匹配了(i)为在自动机上的(j)位置，不卡/卡上界
卡上界是一个很神奇的东西，代表这一位和之前的所有位都和上界相等
如果一个状态卡着上界，我们往下选择的数只能比上界这一位上的数小或者相等，如果相等则继续卡上界，否咋就不卡上界
而如果没有卡上界的话，我们往下选什么都可以啦
而放到(AC)机上无非就是看看这个位置在(fail)树上到根的路径有没有结束标记就好了
但是这样就挂了，因为我们并没有考虑前导(0)的情况
于是多来一维状态，表示是否有前导(0)，如果是前面一直是前导(0)之后继续填(0)我们就直接让其回到根上去
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define re register
#define LL long long
#define maxn 1505
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define pt putchar(1)
const int mod=1e9+7;
int son[maxn][10],f[maxn],fail[maxn];
int dp[1205][1500][2][2];
char S[maxn],T[maxn];
int a[maxn];
int n,L,cnt_1,F[11];
inline void ins()
{
scanf("%s",T+1);
int now=0;
int len=strlen(T+1);
for(re int i=1;i<=len;i++)
{
if(!son[now][T[i]-'0']) son[now][T[i]-'0']=++cnt_1;
now=son[now][T[i]-'0'];
}
f[now]=1;
}
inline void Build()
{
std::queue<int> q;
for(re int i=0;i<10;i++) if(son[0][i]) q.push(son[0][i]);
while(!q.empty())
{
int k=q.front();
q.pop();
f[k]|=f[fail[k]];
for(re int i=0;i<10;i++)
if(son[k][i]) fail[son[k][i]]=son[fail[k]][i],q.push(son[k][i]);
else son[k][i]=son[fail[k]][i];
}
}
int main()
{
scanf("%s",S+1),scanf("%d",&n);
for(re int i=1;i<=n;i++) ins();
Build();L=strlen(S+1);
for(re int i=1;i<=L;i++) a[i]=S[i]-'0';
dp[0][0][1][0]=1;
for(re int i=0;i<L;i++)
for(re int j=0;j<=cnt_1;j++)
for(re int o=0;o<=1;o++)
for(re int p=0;p<=1;p++)
{
if(!dp[i][j][o][p]) continue;
for(re int k=1;k<10;k++)
{
if(f[son[j][k]]) continue;
if(!o) dp[i+1][son[j][k]][0][1]=(dp[i+1][son[j][k]][0][1]+dp[i][j][o][p])%mod;
else
{
if(k<a[i+1]) dp[i+1][son[j][k]][0][1]=(dp[i+1][son[j][k]][0][1]+dp[i][j][o][p])%mod;
else if(a[i+1]==k) dp[i+1][son[j][k]][1][1]=(dp[i+1][son[j][k]][1][1]+dp[i][j][o][p])%mod;
}
}
if(p)
{
re int k=0;
if(F[k]) continue;
if(f[son[j][k]]) continue;
if(!o) dp[i+1][son[j][k]][0][1]=(dp[i+1][son[j][k]][0][1]+dp[i][j][o][p])%mod;
else
{
if(k<a[i+1]) dp[i+1][son[j][k]][0][1]=(dp[i+1][son[j][k]][0][1]+dp[i][j][o][p])%mod;
else if(a[i+1]==k) dp[i+1][son[j][k]][1][1]=(dp[i+1][son[j][k]][1][1]+dp[i][j][o][p])%mod;
}
}
else
{
re int k=0;
dp[i+1][0][0][0]=(dp[i+1][0][0][0]+dp[i][j][o][p])%mod;
}
}
int ans=0;
for(re int i=0;i<=cnt_1;i++) ans=(ans+dp[L][i][0][1]+dp[L][i][1][1])%mod;
printf("%d
",ans);
return 0;
}