bzoj3530 [SDOI2014]数数

Description

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

Input

    输入的第一行包含整数N。
    接下来一行一个整数M，表示S中元素的数量。
    接下来M行，每行一个数字串，表示S中的一个元素。

Output

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

Sample Input

Sample Output

HINT

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

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

Source

AC自动机上的DP

只比trie树上的dp稍麻烦一点。

先建好trie树，设置好AC自动机，然后跑数位DP。先单独处理数长度小于N长度的情况，此时不需要考虑最高位限制。之后处理数长度等于N长度的情况，此时最高位有没有填满要分开决策。

具体看代码：

  1 /*by SilverN*/
  2 #include
  3 #include
  4 #include
  5 #include
  6 #include
  7 #include
  8 using namespace std;
  9 const int mod=1e9+7;
 10 int t[1510][11],cnt=1;
 11 bool end[1510];int fail[1510];
 12 void init(){for(int i=0;i<=9;i++)t[0][i]=1;}
 13 void insert(char s[]){
 14     int rt=1,i,j;
 15     int len=strlen(s);
 16     for(i=0;i