题意: 

问A到B之间的所有整数，转换成BCD Code后，

有多少个不包含属于给定病毒串集合的子串,A,B <=10^200,病毒串总长度<= 2000.

BCD码这个在数字电路课上讲了，题干也讲的很详细。

 

数位DP的实现是通过0~9 ,并不是通过BCD码

所有我们需要先把字串放入AC自动机，建立一个BCD数组

因为BCD码是一个4位二进制数，但是tire图上全是0，1，

所以对于一个数字，我们的要在转移4次，

如果中间出现了病毒串就return -1 表示不能转移，

BCD【i】【j】表示在AC自动机 i 这个节点转移到数字 j 对应的在AC自动机上的节点标号。

  然后就是简单的数位DP了，然而我写搓了，由于没有前导0所以前导0要处理掉。

但是你不转移的时候，不能 bcd[idx][i] != -1 就直接continue ，

因为有0的情况，i==0 但是(bcd[idx][i] == -1) 但是这个0是前导0所以不影响。

 

1 #include 
      
         2 #include 
       

Q; 83 fail[root] = root; 84 for (int i = 0; i < 2; i++) 85 if (next[root][i] == -1) next[root][i] = root; 86 else { 87 fail[next[root][i]] = root; 88 Q.push(next[root][i]); 89 } 90 while (!Q.empty()) { 91 int now = Q.front(); 92 Q.pop(); 93 if (End[fail[now]]) End[now] = 1; 94 for (int i = 0; i < 2; i++) 95 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 96 else { 97 fail[next[now][i]] = next[fail[now]][i]; 98 Q.push(next[now][i]); 99 }100 }101 }102 103 int get_num(int cur, int num) {104 if (End[cur]) return -1;105 int now = cur;106 for (int i = 3; i >= 0; --i) {107 if (End[next[now][1 & (num >> i)]]) return -1;108 now = next[now][1 & (num >> i)];109 }110 return now;111 }112 113 void get_bcd() {114 for (int i = 0; i < cnt; ++i)115 for (int j = 0; j < 10; ++j)116 bcd[i][j] = get_num(i, j);117 }118 119 LL dfs(int pos, int idx, int flag, int limit) {120 if (pos == -1) return 1;121 if (!limit && dp[pos][idx] != -1) return dp[pos][idx];122 int num = limit ? bit[pos] : 9;123 LL ans = 0;124 for (int i = 0; i <= num; ++i) {125 if (flag && i == 0) ans = (ans + dfs(pos - 1, idx, 1, limit && i == num)) % mod;126 else if (bcd[idx][i] != -1) ans = (ans + dfs(pos - 1, bcd[idx][i], 0, limit && i == num)) % mod;127 }128 if (!limit && !flag) dp[pos][idx] = ans;129 return ans;130 }131 132 LL solve() {133 get_bcd();134 int len1 = strlen(num1), len2 = strlen(num2);135 for (int i = len1-1; i>=0; --i) {136 if (num1[i] > '0') {137 num1[i]--;138 break;139 } else num1[i] = '9';140 }141 for (int i = 0; i < len1; ++i) bit[i] = num1[len1 - 1 - i] - '0';142 LL ans1 = dfs(len1 - 1, 0, 1, 1);143 for (int i = 0; i < len2; ++i) bit[i] = num2[len2 - 1 - i] - '0';144 LL ans2 = dfs(len2 - 1, 0, 1, 1);145 return (ans2 - ans1 + mod) % mod;146 }147 148 void debug() {149 for (int i = 0; i < cnt; i++) {150 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);151 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);152 printf("]\n");153 }154 }155 } ac;156 157 int main() {158 // FIN;159 sfi(T);160 while (T--) {161 sfi(n);162 ac.init();163 for (int i = 0; i < n; ++i) {164 sfs(buf);165 ac.insert(buf);166 }167 ac.build();168 sffs(num1, num2);169 mem(dp, -1);170 printf("%lld\n", ac.solve());171 }172 return 0;173 }