$ACAM+数位DP$
$f[pos][node]$表示当前匹配到第$pos$位,在$ACAM$结点$node$的方案数。
预处理出每个结点,加入数字$0-9$后是否合法以及到达的结点,可以减小常数。
转移时若合法直接跳到对应结点,否则直接截断搜索。
前导$0$不记$bcd$码,所以需要记录当前是否是前导$0$。
转移方程$f[pos][node] =\sum_{i=0}^9 f[pos-1][to[node][i]] \times ok[node][i]$。
#include <iostream>
#include <cstring>
using namespace std;
const int mod = 1e9 + 9;
int n;
int nums[210], len;
int tr[2010][2], bad[2010], idx;
int q[2010], fail[2010];
int f[210][2010];
int to[2010][10];
int ok[2010][10];
string bcd[] = {
"0000",
"0001",
"0010",
"0011",
"0100",
"0101",
"0110",
"0111",
"1000",
"1001"
};
void init() {
for (int i = 0; i <= idx; i++)
tr[i][0] = tr[i][1] = fail[i] = 0;
idx = 0;
memset(bad, false, sizeof bad);
memset(f, -1, sizeof f);
}
void insert() {
string s;
cin >> s;
int p = 0;
for (int i = 0; s[i]; i++) {
int u = s[i] - '0';
if (!tr[p][u]) tr[p][u] = ++idx;
p = tr[p][u];
}
bad[p] = true;
}
void build() {
int tt = -1, hh = 0;
for (int i = 0; i < 2; i++)
if (tr[0][i])
q[++tt] = tr[0][i];
while (hh <= tt) {
int t = q[hh++];
for (int i = 0; i < 2; i++) {
int& p = tr[t][i];
if (!p) p = tr[fail[t]][i];
else {
fail[p] = tr[fail[t]][i];
q[++tt] = p;
}
}
bad[t] |= bad[fail[t]];
}
}
int dfs(int pos, int node, int lim, int lead) {
if (!pos) return 1;
int& v = f[pos][node];
if (!lim && !lead && ~v) return v;
int upper = lim ? nums[pos] : 9, res = 0;
for (int i = 0; i <= upper; i++) {
if (lead && !i) {
(res += dfs(pos - 1, node, lim & i == upper, 1)) %= mod;
}
else if (ok[node][i]) {
(res += dfs(pos - 1, to[node][i], lim & i == upper, lead & !i)) %= mod;
}
}
return lim ? res : (lead ? res : v = res);
}
int dp(string s) {
len = 0;
for (int i = s.size() - 1; ~i; i--)
nums[++len] = s[i] - '0';
return dfs(len, 0, 1, 1);
}
bool check(string& s) {
int p = 0;
for (auto& c : s) {
int u = c - '0';
if (!ok[p][u]) return false;
p = to[p][u];
}
return true;
}
void solve() {
init();
int n;
cin >> n;
while (n--) insert();
build();
for (int i = 0; i <= idx; i++) {
for (int j = 0; j <= 9; j++) {
int p = i;
ok[i][j] = true;
for (int k = 0; k < 4; k++) {
int u = bcd[j][k] - '0';
p = tr[p][u];
if (bad[p]) ok[i][j] = false;
}
to[i][j] = p;
}
}
string a, b;
cin >> a >> b;
cout << (dp(b) - dp(a) + check(a) + mod) % mod << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) solve();
return 0;
}