1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 1509 5 #define MO 1000000007 6 #define ll long long 7 using namespace std; 8 char a[M]; 9 int b[M],c[M],n,shu[M][10],tot=1,m,n1,fail[M],q[M],f[1202][1505][3];10 ll ans;11 bool bo[M];12 void dp(int a1)13 {14     for(int i=1;i<=tot;i++)15       for(int l=0;l<=1;l++)16        {17         if(bo[i]||!f[a1-1][i][l])18           continue;19         for(int j=0;j<=9;j++)20           {21             int k=i;22             for(;!shu[k][j];k=fail[k]);23               f[a1][shu[k][j]][l+j>b[a1]]=(f[a1][shu[k][j]][l+j>b[a1]]+f[a1-1][i][l])%MO;24             if(!j)25               f[a1][shu[k][j]][2]=(f[a1][shu[k][j]][2]+f[a1-1][i][l])%MO;26           }27        }28     return;29 }30 int main()31 {32     scanf("%s",a+1);33     n=strlen(a+1);34     for(int i=1;i<=n;i++)35       b[n-i+1]=a[i]-'0';36     scanf("%d",&m);37     for(int i=1;i<=m;i++)38       {39         scanf("%s",a+1);40         n1=strlen(a+1);41         for(int j=1;j<=n1;j++)42           c[n1-j+1]=a[j]-'0';43         int now=1;44         for(int j=1;j<=n1;j++)45           if(shu[now][c[j]])46             now=shu[now][c[j]];47           else48             {49                 shu[now][c[j]]=++tot;50                 now=tot;51             }52         bo[now]=1;53       }54     for(int i=0;i<=9;i++)55       shu[0][i]=1;56     int h=0,t=1;57     q[1]=1;58     for(;h
       
      
     

AC自动机上跑数位DP