【传送门：BZOJ3530】
简要题意：
给出m个数，要求求出不含任意一个数的长度至多为n的数的数量
题解：
这道题比文本生成器要复杂一点，就是因为它的位数不确定，且不可以含有前导0
所以我们用数位DP的思想来做
设f[i][j][k]为当前长度为i且走到AC自动机的第j个点时，如果k=0，则表示仍未到顶格，k=1则表示到了顶格，这种状态下的数的数量
只要在走的时候判断前导零的情况就可以了
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int Mod=1000000007; struct trie { int c[11],s,fail; }t[2100];int tot,root; void clean(int x) { memset(t[x].c,-1,sizeof(t[x].c)); t[x].s=0; } char st[2100]; void bt() { int x=0,len=strlen(st+1); for(int i=1;i<=len;i++) { int y=st[i]-'0'; if(t[x].c[y]==-1) clean(++tot),t[x].c[y]=tot; x=t[x].c[y]; } t[x].s=1; } int list[2100]; void bfs() { list[1]=0; int head=1,tail=1; while(head<=tail) { int x=list[head]; for(int i=0;i<=9;i++) { int son=t[x].c[i]; if(son==-1) continue; if(x==0) t[son].fail=0; else { int j=t[x].fail; while(j!=0&&t[j].c[i]==-1) j=t[j].fail; t[son].fail=max(0,t[j].c[i]); if(t[t[son].fail].s==1) t[son].s=1; } list[++tail]=son; } head++; } } int a[2100]; int f[2100][2100][2]; int main() { scanf("%s",st+1); int n=strlen(st+1); for(int i=1;i<=n;i++) a[i]=st[i]-'0'; int m; scanf("%d",&m); tot=0;clean(0); for(int i=1;i<=m;i++) { scanf("%s",st+1); bt(); } bfs(); for(int i=1;i<=a[1];i++) { int x=t[0].c[i]; if(x==-1) x=0; if(i<a[1]) f[1][x][0]++; if(i==a[1]) f[1][x][1]++; } for(int i=2;i<=n;i++) { for(int j=1;j<=9;j++) { int x=t[0].c[j]; if(x==-1) x=0; f[i][x][0]++; } for(int j=0;j<=tot;j++) { if(t[j].s==0) { for(int k=0;k<=9;k++) { int son=j; while(son!=0&&t[son].c[k]==-1) son=t[son].fail; son=t[son].c[k]; if(son==-1||t[son].s==0) { if(i==1&&k==0) continue; if(son==-1) son=0; f[i][son][0]=(f[i][son][0]+f[i-1][j][0])%Mod; if(k<a[i]) f[i][son][0]=(f[i][son][0]+f[i-1][j][1])%Mod; if(k==a[i]) f[i][son][1]=(f[i][son][1]+f[i-1][j][1])%Mod; } } } } } int ans=0; for(int i=0;i<=tot;i++) if(t[i].s==0) ans=(ans+f[n][i][0]+f[n][i][1])%Mod; printf("%d ",ans); return 0; }