ZOJ 3494 BCD 코드(AC 로봇 + 디지털 DP, 레벨 5)

BCD Code
Time Limit: 5 Seconds     
Memory Limit: 65536 KB
Binary-coded decimal (BCD) is an encoding for decimal numbers in which each digit is represented by its own binary sequence. To encode a decimal number using the common BCD encoding, each decimal digit is stored in a 4-bit nibble:

Decimal:    0     1     2     3     4     5     6     7     8     9
BCD:     0000  0001  0010  0011  0100  0101  0110  0111  1000  1001

Thus, the BCD encoding for the number 127 would be:

 0001 0010 0111

We are going to transfer all the integers from A to B, both inclusive, with BCD codes. But we find that some continuous bits, named forbidden code, may lead to errors. If the encoding of some integer contains these forbidden codes, the integer can not be transferred correctly. Now we need your help to calculate how many integers can be transferred correctly.
Input
There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.
The first line of each test case contains one integer N, the number of forbidden codes ( 0 ≤ N ≤ 100). Then N lines follow, each of which contains a 0-1 string whose length is no more than 20. The next line contains two positive integers A and B. Neither A or B contains leading zeros and 0 < A ≤ B < 10200.
Output
For each test case, output the number of integers between A and B whose codes do not contain any of the N forbidden codes in their BCD codes. For the result may be very large, you just need to output it mod 1000000009.
Sample Input

3
1
00
1 10
1
00
1 100
1
1111
1 100

Sample Output

3
9
98

References

http://en.wikipedia.org/wiki/Binary-coded_decimal

Author:
GUAN, Yao
사고방식: 먼저 AC 자동기로 포비든의 BCD 코드를 기록한 다음에 10진법의 BCD 이동 상태를 미리 처리한다.
그리고 간단한 디지털 DP 하나면 돼요.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define clr(f,z) memset(f,z,sizeof(f))
#define LL long long
using namespace std;
const int mm=2013;
const int MOD=1000000009;
class AC
{
public://f     
  int ch[mm][2],f[mm];
  bool val[mm];
  int sz;
  AC()
  {
    sz=1;clr(ch[0],0);val[0]=0;
  }
  void clear()
  {
    sz=1;clr(ch[0],0);val[0]=0;
  }
  int idx(char x)
  {
    return x-'0';
  }
  void insert(char*s)
  {
    int u=0,c;
    for(int i=0;s[i];++i)
    {
      c=idx(s[i]);
      if(!ch[u][c])//add a node
      { val[sz]=0;
        clr(ch[sz],0);ch[u][c]=sz++;
      }
      u=ch[u][c];
    }
    val[u]=1;
  }
  void getFail()
  { int u=0,v,r;
    queue<int>Q;
    f[0]=0;
    FOR(i,0,1)
    if(ch[0][i])Q.push(ch[0][i]),f[ ch[0][i] ]=0;

    while(!Q.empty())
    {
      r=Q.front();Q.pop();
      val[r]|=val[ f[r] ];//       
      FOR(c,0,1)
      {
        u=ch[r][c];
        if(!u){ ch[r][c]=ch[ f[r] ][c]; continue;}
        Q.push(u);
        v=f[r];
        while(v&&!ch[v][c])v=f[v];//        FAIl
        f[u]=ch[v][c];
      }
    }
  }
  int bcd[mm][10];
  int chage(int fa,int num)
  {
    if(val[fa])return -1;
    int cur=fa;
    for(int i=3;i>=0;--i)
    {
      if(val[ ch[cur][(num>>i)&1] ])return -1;
      cur=ch[cur][ (num>>i)&1 ];
    }
    return cur;
  }
  void get_BCD()///          
  {
    FOR(i,0,sz-1)
    FOR(j,0,9)
    bcd[i][j]=chage(i,j);
  }
  void BCD_out()
  {
    FOR(i,0,sz-1)
    FOR(j,0,9)
    printf("bcd=%d %d %d 
",i,j,bcd[i][j]);
  }
  LL dp[210][mm];int bit[210],pos;
  LL DP(int pp,int s,bool big,bool nozero)
  {
    if(pp == 0)return 1;
    if(big&&dp[pp][s]!=-1)return dp[pp][s];
    LL ans = 0;
    if(nozero)
    {
      if(bcd[s][0]!=-1)ans += DP(pp-1,bcd[s][0],big || bit[pp]!=0,nozero);
        ans %= MOD;
    }
    else
    {
        ans += DP(pp-1,s,big || bit[pp]!=0,nozero);
        ans %= MOD;
    }
    int kn= big?9:bit[pp];
    for(int i = 1;i<=kn;i++)
    {
        if(bcd[s][i]!=-1)
        {
            ans += DP(pp-1,bcd[s][i],big||i!=kn,1);
            ans %=MOD;
        }
    }
    if(big&&nozero)dp[pp][s] = ans;///important big is not mean nozero
    return ans;
  }
  LL get(char*s)
  { clr(dp,-1);
    pos=0;
    int len=strlen(s);

    for(int i=len-1;i>=0;--i)
    bit[++pos]=s[i]-'0';
    //return dfs(pos,0,1,1);
    return DP(pos,0,0,0);
  }
}ac;
char s[222];
int main()
{
  int cas,n;
  while(~scanf("%d",&cas))
  {
    FOR(ca,1,cas)
    { ac.clear();
      scanf("%d",&n);
      FOR(i,1,n)
      {
        scanf("%s",s);
        ac.insert(s);
      }
      ac.getFail();
      ac.get_BCD();
      //ac.BCD_out();
      LL ans=0;
      scanf("%s",s);
      int len=strlen(s);
      for(int i=len-1;i>=0;--i)
        if(s[i]>'0'){--s[i];break;}
        else s[i]='9';
      //cout<<s<<endl;
      ans-=ac.get(s);
      scanf("%s",s);
      ans+=ac.get(s);
      ans%=MOD;
      if(ans<0)ans+=MOD;
      printf("%lld
",ans);
    }
  }
}