题目描述

我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。

    给定N和S，计算不大于N的幸运数个数。

输入

    输入的第一行包含整数N。

    接下来一行一个整数M，表示S中元素的数量。

    接下来M行，每行一个数字串，表示S中的一个元素。

输出

    输出一行一个整数，表示答案模109+7的值。

样例输入

20

3

2

3

14

样例输出

14

提示

 下表中l表示N的长度，L表示S中所有串长度之和。

1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500

 

这道题和比较像，建议先做一下那道题。虽然是一道AC自动机的题但重点是dp，因为不只有位数限制，每一位还有限制数值，所以不能只用f[i][j]表示第i位走到了j节点。因为有限制值所以我们不妨在前面再加一维变成f[k][i][j](k=0或k=1)，f[0][i][j]表示第i为走到j节点需要受限制(即前几位都等于每一位限制值)，f1[1][i][j]则表示第i位走到j节点不受限制(即前几位有至少一位低于限制值)。当枚举f[0][i][j]时如果j节点所代表的数字小于第i位的限制值，那就可以转移到f[1][i+1][x](x为j的子节点).对于f[0][i][j],因为这一位受限制，所以下一位也要相应受限制，即f[0][i][j]转移到f[0][i+1][x].对于f[1][i][j],因为这一位不受限制,下一位一定不受限制,所以从f[1][i][j]转移到f[1][i+1][x]。

最后附上代码。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;struct tree{ int fail; int vis[11]; int end;}a[1600];char s[1600];char t[1250];int cnt;int n;int m;long long ans;long long f[3][1250][1600];int mod=1e9+7;void build(char *s){ int l=strlen(s); int now=0; for(int i=0;i
            

q; for(int i=0;i<10;i++) { if(a[0].vis[i]!=0) { a[a[0].vis[i]].fail=0; q.push(a[0].vis[i]); } } while(!q.empty()) { int now=q.front(); q.pop(); for(int i=0;i<10;i++) { if(!a[now].vis[i]) { a[now].vis[i]=a[a[now].fail].vis[i]; continue; } a[a[now].vis[i]].fail=a[a[now].fail].vis[i]; a[a[now].vis[i]].end|=a[a[a[now].fail].vis[i]].end; q.push(a[now].vis[i]); } }}int main(){ scanf("%s",t+1); m=strlen(t+1); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s); build(s); } getfail(); for(int i=0;i