ZOJ-3494 BCD Code (ac自动机+数位dp)

题目链接

Problem Description

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

31001 101001 100111111 100

Sample Output

3998

AC

• 涉及到多个字符串的匹配问题，AC自动机
• 初始化AC自动机，这里有一个处理，就是如果当前节点的fail指向终点的话，那么这个节点也标记为终点（end[pos]++)，一个长的字符串可能包含一个短的字符串
• 预处理一个BCD[i][j]，表示在AC自动机的第i个位置后添加数字j，如果不能添加就赋值为-1，如果可以赋值为新的位置
• 数位dp

#include <iostream>#include <stdio.h>#include <map>#include <vector>#include <set>#include <queue>#include <stack>#include <cstring>#include <cmath>#include <iomanip>#include <algorithm>#define N 2001#define mem(a, b) memset(a, b, sizeof(a))typedef long long LL;using namespace std;struct Trie{int next[N][2], fail[N], end[N];int L, root;int newnode() {for (int i = 0; i < 2; ++i)next[L][i] = -1;end[L++] = 0;return L-1;}void init() {L = 0;root = newnode();}void insert(char s[]) {int len = strlen(s);int now = root;for (int i = 0; i < len; ++i) {if (next[now][s[i]-'0'] == -1)next[now][s[i]-'0'] = newnode();now = next[now][s[i]-'0'];}end[now]++;}void build() {queue<int> que;fail[root] = root;for (int i = 0; i < 2; ++i){if (next[root][i] == -1)next[root][i] = root;else {fail[next[root][i]] = root;que.push(next[root][i]);}}while (!que.empty()) {int now = que.front();que.pop();if (end[fail[now]]) end[now]++; // 至关重要的一句for (int i = 0; i < 2; ++i) {if (next[now][i] == -1)next[now][i] = next[fail[now]][i];else {fail[next[now][i]] = next[fail[now]][i];que.push(next[now][i]);}}}}}ac;char s1[201], s2[201];int bcd[2001][10];int dp[201][2001];int dig[201];const int mod = 1e9 + 9;int find(int pos, int num) {if (ac.end[pos]) return -1;for (int i = 3; i >= 0; --i){int t = ac.next[pos][(num >> i) & 1];if (ac.end[t]) return -1;pos = t;}return pos;}void init() {for (int i = 0; i < ac.L; ++i) {for (int j = 0; j < 10; ++j) {bcd[i][j] = find(i, j);}}}int dfs(int len, int sta, bool top, bool zero) {if (sta == -1) return 0;if (!len) return 1;if (!top && dp[len][sta] != -1 && !zero) return dp[len][sta];int t = top ? dig[len] : 9;int ans = 0;for (int i = 0; i <= t; ++i) {if (i == 0 && zero)ans += dfs(len-1, sta, top && i==t, zero && !i);elseans += dfs(len-1, bcd[sta][i], top && i==t, zero && !i);ans %= mod;}if (!top && !zero)dp[len][sta] = ans;return ans;}int solve(char s[]) {int len = strlen(s);for (int i = 1; i <= len; ++i) {dig[i] = s[len-i] - '0';}return dfs(len, 0, 1, 1);}int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endifint t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);ac.init();for (int i = 0; i < n; ++i) {scanf("%s", s1);ac.insert(s1);}ac.build();init();mem(dp, -1);scanf("%s%s", s1, s2);int len = strlen(s1);for (int i = len - 1; i >= 0; --i) {if (s1[i] == '0') s1[i] = '9';else {s1[i]--;break;}}int ans = solve(s2) - solve(s1);ans = (ans + mod) % mod;printf("%d\n", ans);}return 0;}

总结

以上是生活随笔为你收集整理的ZOJ-3494 BCD Code (ac自动机+数位dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。