【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
", ans);

135     }

136     return 0;

137 }