【ZOJ】3494 BCD Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define MOD 1000000009
  5 #define MAXN 2010
  6 #define MAXM 210
  7 using namespace std;
  8 struct Trie {
  9     bool end;
 10     int fail, next[2];
 11     void Init() {
 12         end = false;
 13         fail = 0;
 14         memset(next, 0, sizeof(next));
 15     }
 16 };
 17 Trie tree[MAXN];
 18 int size, bcd[MAXN][10], digit[MAXM], dp[MAXN][MAXM];
 19 char str[MAXM];
 20 void Insert(char *s) {
 21     int now, t;
 22     for (now = 0; *s; s++) {
 23         t = *s - '0';
 24         if (!tree[now].next[t]) {
 25             tree[++size].Init();
 26             tree[now].next[t] = size;
 27         }
 28         now = tree[now].next[t];
 29     }
 30     tree[now].end = true;
 31 }
 32 void BFS() {
 33     int now, i, p;
 34     queue<int> q;
 35     q.push(0);
 36     while (!q.empty()) {
 37         now = q.front();
 38         q.pop();
 39         for (i = 0; i < 2; i++) {
 40             if (tree[now].next[i]) {
 41                 p = tree[now].next[i];
 42                 q.push(p);
 43                 if (now) {
 44                     tree[p].fail = tree[tree[now].fail].next[i];
 45                     tree[p].end |= tree[tree[p].fail].end;
 46                 }
 47             } else
 48                 tree[now].next[i] = tree[tree[now].fail].next[i];
 49         }
 50     }
 51 }
 52 int NEXT(int now, int val) {
 53     if (tree[now].end)
 54         return -1;
 55     int i;
 56     for (i = 3; i >= 0; i--) {
 57         now = tree[now].next[(val >> i) & 1];
 58         if (tree[now].end)
 59             return -1;
 60     }
 61     return now;
 62 }
 63 void BCD() {
 64     int i, j;
 65     for (i = 0; i <= size; i++) {
 66         for (j = 0; j < 10; j++)
 67             bcd[i][j] = NEXT(i, j);
 68     }
 69 }
 70 int DFS(int rt, int pos, bool bound, bool zero) {
 71     if (pos < 0)
 72         return 1;
 73     if (!bound && dp[rt][pos] != -1)
 74         return dp[rt][pos];
 75     int i, limit, ans;
 76     ans = 0;
 77     limit = bound ? digit[pos] : 9;
 78     if (zero && pos) {
 79         ans += DFS(rt, pos - 1, bound && limit == 0, true);
 80         if (ans >= MOD)
 81             ans -= MOD;
 82     } else {
 83         if (bcd[rt][0] != -1) {
 84             ans += DFS(bcd[rt][0], pos - 1, bound && limit == 0, false);
 85             if (ans >= MOD)
 86                 ans -= MOD;
 87         }
 88     }
 89     for (i = 1; i <= limit; i++) {
 90         if (bcd[rt][i] != -1) {
 91             ans += DFS(bcd[rt][i], pos - 1, bound && i == limit, false);
 92             if (ans >= MOD)
 93                 ans -= MOD;
 94         }
 95     }
 96     if (!bound)
 97         dp[rt][pos] = ans;
 98     return ans;
 99 }
100 int DoIt() {
101     int i, len;
102     len = strlen(str);
103     for (i = 0; i < len; i++)
104         digit[len - i - 1] = str[i] - '0';
105     return DFS(0, len - 1, true, true);
106 }
107 int main() {
108     int c, n, i, len, ans;
109     scanf("%d", &c);
110     while (c--) {
111         tree[0].Init();
112         memset(dp, -1, sizeof(dp));
113         scanf("%d", &n);
114         for (size = 0; n--;) {
115             scanf(" %s", str);
116             Insert(str);
117         }
118         BFS();
119         BCD();
120         scanf(" %s", str);
121         len = strlen(str);
122         for (i = len - 1; i >= 0; i--) {
123             if (str[i] > '0') {
124                 str[i]--;
125                 break;
126             } else
127                 str[i] = '9';
128         }
129         ans = -DoIt();
130         scanf(" %s", str);
131         ans += DoIt();
132         if (ans < 0)
133             ans += MOD;
134         printf("%d\n", ans);
135     }
136     return 0;
137 }