bzoj [Sdoi2014]数数 AC自动机上dp

[Sdoi2014]数数

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 1264 Solved: 636
[Submit][Status][Discuss]

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

20
3
2
3
14

Sample Output

HINT

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

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

Source

Round 1 day 1

AC自动机建好后f[i][j][k]表示i这个点j长度k=0表示小于，1表示等于

这样转移很好转移 IL的复杂度随便跑，

虑到不能有前导零，所以填每一位的时候可以把根节点单独转移一次1~9

  1 #pragma GCC optimzie(2)
  2 #pragma G++ optimize(2)
  3 #include<cstring>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<cstdio>
  7 #include<algorithm>
  8 #include<queue>
  9 
 10 #define ll long long
 11 #define N 2007
 12 #define mod 1000000007
 13 using namespace std;
 14 inline int read()
 15 {
 16     int x=0,f=1;char ch=getchar();
 17     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
 18     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
 19     return x*f;
 20 }
 21 
 22 int m,len,l;
 23 ll ans;
 24 struct Node
 25 {
 26     int c[11],suf;
 27     bool flag;
 28 }trie[N];
 29 int cnt=1,rt=1;
 30 ll f[1207][1507][2];
 31 char ch[N],n[N];
 32 
 33 void insert()
 34 {
 35     int now=rt;
 36     for (int i=1;i<=len;i++)
 37         if(trie[now].c[ch[i]-'0'])now=trie[now].c[ch[i]-'0'];
 38         else
 39         {
 40             trie[now].c[ch[i]-'0']=++cnt;
 41             now=cnt;
 42         }
 43     trie[now].flag=true;
 44 }
 45 void make_AC()
 46 {
 47     for (int i=0;i<10;i++)
 48         trie[0].c[i]=1;
 49     queue<int>q;q.push(1);
 50     trie[1].suf=0;
 51     while(!q.empty())
 52     {
 53         int u=q.front();q.pop();
 54         for (int i=0;i<10;i++)
 55             if(trie[u].c[i])
 56             {
 57                 trie[trie[u].c[i]].suf=trie[trie[u].suf].c[i];
 58                 if(trie[trie[trie[u].c[i]].suf].flag)trie[trie[u].c[i]].flag=true;
 59                 q.push(trie[u].c[i]);
 60             }
 61             else trie[u].c[i]=trie[trie[u].suf].c[i];
 62     }
 63 }
 64 void solve()
 65 {
 66     /*f[0][1][1]=1;
 67     for (int i=0;i<l;i++)
 68         for (int j=1;j<=cnt;j++)
 69         {
 70             if (f[i][j][1]&&!trie[j].flag)
 71             {
 72                 for (int k=0;k<10;k++)
 73                     if (n[i+1]-'0'>k)(f[i+1][trie[j].c[k]][0]+=f[i][j][1])%=mod;
 74                     else if(n[i+1]-'0'==k)(f[i+1][trie[j].c[k]][1]+=f[i][j][1])%=mod;
 75             }
 76             if(f[i][j][0]&&!trie[j].flag)
 77             {
 78                 for (int k=0;k<10;k++)
 79                     (f[i+1][trie[j].c[k]][0]+=f[i][j][0])%=mod;
 80             }
 81         }*/
 82     for (int i=1;i<=l;i++)
 83     {
 84         for (int z=1,v=trie[1].c[z];z<=9;v=trie[1].c[++z])
 85         {
 86             if(i!=1||z<n[i]-'0')(f[i][v][0]+=1)%=mod;
 87             else if(z==n[i]-'0')(f[i][v][1]+=1)%=mod;
 88         }
 89         for (int j=1;j<=cnt;j++)
 90             if(!trie[j].flag)
 91                 for (int c=0,v=trie[j].c[c];c<=9;v=trie[j].c[++c])
 92                 {
 93                     (f[i][v][0]+=f[i-1][j][0])%=mod;
 94                     if(c<n[i]-'0')(f[i][v][0]+=f[i-1][j][1])%=mod;
 95                     else if(c==n[i]-'0')(f[i][v][1]+=f[i-1][j][1])%=mod;
 96                 }
 97     }
 98         
 99     for (int i=1;i<=cnt;i++)
100         if(!trie[i].flag)(ans+=f[l][i][0]+f[l][i][1])%=mod;
101     printf("%lld",ans);
102 }
103 int main()
104 {
105     scanf("%s",n+1);l=strlen(n+1);
106     m=read();
107     for (int i=1;i<=m;i++)
108     {
109         scanf("%s",ch+1),len=strlen(ch+1);
110         insert();
111     }
112     make_AC(),solve();
113 }