前言
又是zzy讲课，果然zzy讲课就算是字符串专题也涵盖了dp呢
题意
给定长度为 n 的数字串 s 和长度为 d 的不含前导零的数字串 $x,y(x\le y)$
求存在长度至少为 $\left\lfloor\frac{d}{2}\right\rfloor$ 的子串是 s 的子串的数字串 $t \in [x,y]$ 的数量。
$n \le 10^3$，$d \le 50$，答案对 $10^9+7$ 取模。
题解
首先是一个暴力的思路，对于所有长度为 $\left\lfloor\frac{d}{2}\right\rfloor$ 的 s 的子串，建一个AC自动机，建好后，对所有 $t \in [x,y]$ 跑 AC自动机统计答案
考虑到 $x,y$ 的范围，容易想到数位DP，对于 $t \in [x,y]$ ，可以差分处理
考虑我们需要记录的值：
当前数字是第几位
当前数字是什么
我们当前走到AC自动机的哪个结点
当前状态是否已经合法
同时为了合法的转移，我们还需要记录是否达到瓶颈( 即之前的位数都与边界值相等)
所以我们得到了状态 $f[i][k][ft1][now][ft2]$
此时我们空间复杂度为 $O(40\times d^2n)$ 估算一下空间大小，难以接受，考虑滚动数组
于是最终我们得到的状态转移方程为
$$
\begin{cases}
f[k][1][v][end[v]|ft]+=f[j][1][u][ft]\quad(k=x[i],j=x[i-1])\\
f[k][0][v][end[v]|ft]+=f[j][1][u][ft]\quad(k<x[i],j=x[i-1])\\
f[k][0][v][end[v]|ft]+=f[j][0][u][ft]
\end{cases}
$$
通过转移方程，我们需要枚举
当前的位数
当前的数字
之前的数字
之前走到了哪个结点
当前的状态（合法/不合法）
时间复杂度 $O(200\times d^2n)$ 但有许多无用情况会被枚举，这些情况我们可以通过判断跳过，时间上远达不到此上界
$$
\large\color{grey}{\text{Talk is cheap , show you the code}}
$$
代码
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<cstring>
#include<time.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=50005;
const int inf=0x3f3f3f3f;
const int p=1e9+7;
char s[maxn];
char tmp[maxn];
struct node
{
int ch[10],pos,fail;
}tr[maxn];
int n,d,tot,a[maxn],b[maxn],rt=0;
ll ans,f[10][2][maxn][2],g[10][2][maxn][2];
queue<int>q;
inline void insert(int st)
{
int u=rt;
for(register int i=st;i<st+d/2;++i)
{
int c=s[i]-'0';
if(!tr[u].ch[c])tr[u].ch[c]=++tot;
u=tr[u].ch[c];
}
tr[u].pos=true;
}
inline void get_fail(void)
{
for(register int i=0;i<10;++i)if(tr[rt].ch[i])q.push(tr[rt].ch[i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(register int i=0;i<10;++i)
if(tr[u].ch[i])
tr[tr[u].ch[i]].fail=tr[tr[u].fail].ch[i],q.push(tr[u].ch[i]);
else
tr[u].ch[i]=tr[tr[u].fail].ch[i];
}
}
signed main(void)
{
cin>>s;
cin>>tmp;
n=strlen(s),d=strlen(tmp);
for(register int i=0;i<d;++i)a[i]=tmp[i]-'0';
cin>>tmp;
for(register int i=0;i<d;++i)b[i]=tmp[i]-'0';
--a[d-1];
for(register int i=d-1;i>0;--i)
if(a[i]<0)a[i]=a[i]+10,--a[i-1];
for(register int i=0;i<n;++i)
{
if(i+d/2>n)break;
insert(i);
}
get_fail();
for(register int i=0;i<b[0];++i)g[i][0][tr[rt].ch[i]][tr[tr[rt].ch[i]].pos]=1;
g[b[0]][1][tr[rt].ch[b[0]]][tr[tr[rt].ch[b[0]]].pos]=1;
for(register int i=1;i<d;++i)
{
for(register int u=0;u<=tot;++u)
for(register int j=0;j<10;++j)
{
if(!g[j][1][u][1]&&!g[j][1][u][0]&&!g[j][0][u][0]&&!g[j][0][u][1])continue;
for(register int k=0;k<10;++k)
{
int v=tr[u].ch[k];
for(register int ft=0;ft<2;++ft)
{
if(j==b[i-1]&&k==b[i]) (f[k][1][v][tr[v].pos|ft]+=g[j][1][u][ft])%=p;
else if(k<b[i]&&j==b[i-1]) (f[k][0][v][tr[v].pos|ft]+=g[j][1][u][ft])%=p;
(f[k][0][v][tr[v].pos|ft]+=g[j][0][u][ft])%=p;
}
}
}
for(register int u=0;u<=tot;++u)
for(register int k=0;k<10;++k)
{
g[k][0][u][1]=f[k][0][u][1];
g[k][1][u][1]=f[k][1][u][1];
g[k][0][u][0]=f[k][0][u][0];
g[k][1][u][0]=f[k][1][u][0];
if(i==d-1)(ans+=f[k][0][u][1]+f[k][1][u][1])%=p;
f[k][0][u][1]=f[k][1][u][1]=f[k][0][u][0]=f[k][1][u][0]=0;
}
}
memset(g,0,sizeof g);
int gft=false;
for(register int i=0;i<d;++i)if(a[i]>0)gft=true;
if(gft)
{
for(register int i=0;i<a[0];++i)g[i][0][tr[rt].ch[i]][tr[tr[rt].ch[i]].pos]=-1;
g[a[0]][1][tr[rt].ch[a[0]]][tr[tr[rt].ch[a[0]]].pos]=-1;
for(register int i=1;i<d;++i)
{
for(register int u=0;u<=tot;++u)
for(register int j=0;j<10;++j)
{
if(!g[j][1][u][1]&&!g[j][1][u][0]&&!g[j][0][u][0]&&!g[j][0][u][1])continue;
for(register int k=0;k<10;++k)
{
int v=tr[u].ch[k];
for(register int ft=0;ft<2;++ft)
{
if(j==a[i-1]&&k==a[i]) (f[k][1][v][tr[v].pos|ft]+=g[j][1][u][ft])%=p;
else if(k<a[i]&&j==a[i-1]) (f[k][0][v][tr[v].pos|ft]+=g[j][1][u][ft])%=p;
(f[k][0][v][tr[v].pos|ft]+=g[j][0][u][ft])%=p;
}
}
}
for(register int u=0;u<=tot;++u)
for(register int k=0;k<10;++k)
{
g[k][0][u][1]=f[k][0][u][1];
g[k][1][u][1]=f[k][1][u][1];
g[k][0][u][0]=f[k][0][u][0];
g[k][1][u][0]=f[k][1][u][0];
if(i==d-1)ans=(ans+f[k][0][u][1]+f[k][1][u][1]+p)%p;
f[k][0][u][1]=f[k][1][u][1]=f[k][0][u][0]=f[k][1][u][0]=0;
}
}
}
cout<<ans<<endl;
}
