题目大意
定义一个数的 BCD Code 是它的每个数码的 $4$ 位二进制表示拼接起来。给定 $n$ 个长度不超过 $20$ 的禁忌串和两个正整数 $A, B$，问 $A, B$ 之间有多少数的 BCD Code 不包含禁忌串。
数据范围：$n \le 100, A, B \le 10^{200}$。
思路分析
AC 自动机 + 数位 DP
这里纯粹只是为了贴（两）个板子。
代码实现
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | const int maxn = 200, maxm = 2e3, mod = 1e9 + 9; |
7 | const char *str[] = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001" }; |
8 | int T, n, m, tot, ch[maxm + 3][2], mrk[maxm + 3], fail[maxm + 3], dp[maxn + 3][maxm + 3][2][2]; |
9 | char s[maxn + 3]; |
10 | |
11 | void clear(int x) { |
12 | ch[x][0] = ch[x][1] = mrk[x] = fail[x] = 0; |
13 | } |
14 | |
15 | void insert(char s[], int n) { |
16 | int x = 1; |
17 | for (int i = 1; i <= n; i++) { |
18 | if (!ch[x][s[i] - '0']) { |
19 | clear(++tot); |
20 | ch[x][s[i] - '0'] = tot; |
21 | } |
22 | x = ch[x][s[i] - '0']; |
23 | } |
24 | mrk[x] = 1; |
25 | } |
26 | |
27 | void build() { |
28 | queue<int> Q; |
29 | for (int i = 0; i < 2; i++) { |
30 | if (ch[1][i]) { |
31 | fail[ch[1][i]] = 1; |
32 | Q.push(ch[1][i]); |
33 | } else { |
34 | ch[1][i] = 1; |
35 | } |
36 | } |
37 | while (!Q.empty()) { |
38 | int u = Q.front(); |
39 | Q.pop(); |
40 | mrk[u] |= mrk[fail[u]]; |
41 | for (int i = 0; i < 2; i++) { |
42 | if (ch[u][i]) { |
43 | fail[ch[u][i]] = ch[fail[u]][i]; |
44 | Q.push(ch[u][i]); |
45 | } else { |
46 | ch[u][i] = ch[fail[u]][i]; |
47 | } |
48 | } |
49 | } |
50 | } |
51 | |
52 | void add(int &x, int y) { |
53 | x = (x + y < mod ? x + y : x + y - mod); |
54 | } |
55 | |
56 | int solve(char s[], int n) { |
57 | memset(dp, 0, sizeof(dp)); |
58 | dp[0][1][1][1] = 1; |
59 | for (int i = 1; i <= n; i++) { |
60 | for (int j = 1; j <= tot; j++) { |
61 | for (int k = 0; k < 2; k++) { |
62 | for (int l = 0; l < 2; l++) { |
63 | if (!dp[i - 1][j][k][l]) continue; |
64 | for (int x = 0; x <= (k ? s[i] - '0' : 9); x++) { |
65 | bool flag = true; |
66 | int u = j; |
67 | if (!l || x) { |
68 | const char *s = str[x]; |
69 | for (int t = 0; t < 4; t++) { |
70 | u = ch[u][s[t] - '0']; |
71 | if (mrk[u]) flag = false; |
72 | } |
73 | } |
74 | if (flag) { |
75 | add(dp[i][u][k && (x == s[i] - '0')][l && x == 0], dp[i - 1][j][k][l]); |
76 | } |
77 | } |
78 | } |
79 | } |
80 | } |
81 | } |
82 | int ans = 0; |
83 | for (int i = 1; i <= tot; i++) { |
84 | for (int j = 0; j < 2; j++) { |
85 | add(ans, dp[n][i][j][0]); |
86 | } |
87 | } |
88 | return ans; |
89 | } |
90 | |
91 | int main() { |
92 | scanf("%d", &T); |
93 | while (T--) { |
94 | scanf("%d", &n); |
95 | tot = 1, clear(1); |
96 | for (int i = 1; i <= n; i++) { |
97 | scanf("%s", s + 1); |
98 | m = strlen(s + 1); |
99 | insert(s, m); |
100 | } |
101 | build(); |
102 | scanf("%s", s + 1); |
103 | m = strlen(s + 1); |
104 | for (int i = m; i; i--) { |
105 | if (s[i] == '0') { |
106 | s[i] = '9'; |
107 | } else { |
108 | s[i]--; |
109 | break; |
110 | } |
111 | } |
112 | if (s[1] == '0') { |
113 | m--; |
114 | for (int i = 1; i <= m; i++) { |
115 | s[i] = s[i + 1]; |
116 | } |
117 | } |
118 | int ans = -solve(s, m); |
119 | scanf("%s", s + 1); |
120 | m = strlen(s + 1); |
121 | ans += solve(s, m); |
122 | ans < 0 ? ans += mod : 0; |
123 | printf("%d\n", ans); |
124 | } |
125 | return 0; |
126 | } |