题解 P3311 【[SDOI2014]数数】

看大家好像都写的挺麻烦的？ 关于多子串的东西可以想到AC自动机，可以在上面dp。 $dp_{i,j,0/1}$代表$i\sim n$位数字目前在AC自动机上匹配到节点$j$是否有最高位限制。 最后一位可以像数位dp那样非常简单的转移。 然后有个坑点是$S$中有前导$0$，但是$N$中没有。 有一种简单的处理方法是在建完AC自动机后把边$ch[root][0]$删掉 ------ **Code:** ```cpp #include <cstdio> #include <cstring> const int mod=1e9+7; const int N=1520; inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;} char s[N],t[N]; int ch[N][10],endro[N],fail[N],tot,q[N],l=1,r,bit[N],dp[N][N][2]; void ins() { scanf("%s",s+1); int n=strlen(s+1),now=0; for(int i=1;i<=n;i++) { if(!ch[now][s[i]-'0']) ch[now][s[i]-'0']=++tot; now=ch[now][s[i]-'0']; } endro[now]=1; } void build() { for(int i=0;i<10;i++) if(ch[0][i]) q[++r]=ch[0][i]; while(l<=r) { int now=q[l++]; for(int i=0;i<10;i++) { if(ch[now][i]) fail[q[++r]=ch[now][i]]=ch[fail[now]][i]; else ch[now][i]=ch[fail[now]][i]; } } ch[0][0]=0; } int main() { scanf("%s",t+1); int n=strlen(t+1),m; for(int i=1;i<=n;i++) bit[i]=t[n+1-i]-'0'; scanf("%d",&m); for(int i=1;i<=m;i++) ins(); build(); dp[n+1][0][1]=1; for(int i=n+1;i>1;i--) for(int j=0;j<=tot;j++) for(int l=0;l<=1;l++) for(int k=0,u=l?bit[i-1]:9;k<=u;k++) { int to=ch[j][k]; if(!endro[to]) add(dp[i-1][to][l&k==bit[i-1]],dp[i][j][l]); } int ans=mod-1; for(int i=0;i<=tot;i++) add(ans,dp[1][i][0]),add(ans,dp[1][i][1]); printf("%d\n",ans); return 0; } ```