P13206 [GCJ 2016 Finals] Integeregex

在本题中，一个合法的正则表达式是下列之一。描述中的 $E_1, E_2$ 等表示（不一定不同的）合法正则表达式。 * 一个十进制数字：即 $\mathbf{0}\ \mathbf{1}\ \mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{5}\ \mathbf{6}\ \mathbf{7}\ \mathbf{8}\ \mathbf{9}$ 之一。 * 连接：$E_1 E_2$。 * 并选：$\left(E_1|E_2|\ldots|E_N\right)$，其中至少有两个表达式。注意外层括号是必须的。 * 重复：$\left(E_1\right)^*$。注意外层括号是必须的。 例如，$7$, $23$, $(7)^*$, $(45)^*$, $(1|2|3)$, $((2)^*|3)$, $(1|2|3)$, $((0|1))^*$ 都是合法表达式。$(7)$, $4|5$, $4^*$, $(1|)$, $(0|1)^*$ 都不是。 我们说表达式 $E$ 匹配数字字符串 $D$ 当且仅当下列之一成立： * $E=D$。 * $E=E_1 E_2$，且存在 $D_1, D_2$ 使得 $D=D_1 D_2$ 且 $E_i$ 匹配 $D_i$。 * $E=\left(E_1|E_2|\ldots|E_N\right)$，且至少有一个 $E_i$ 匹配 $D$。 * $E=\left(E_1\right)^*$，且存在若干非负整数 $N$ 及 $D_1, D_2, \ldots, D_N$，使得 $D=D_1 D_2 \ldots D_N$ 且 $E_1$ 匹配每个 $D_i$。特别地，$\left(E_1\right)^*$ 匹配空串。 例如，表达式 $((1|2))^*3$ 匹配 $3, 13, 123, 2221123$ 等字符串，但不匹配 $1234, 3123, 12, 33$ 等。 给定一个合法的正则表达式 $\mathbf{R}$，问有多少个整数在 $[\mathbf{A}, \mathbf{B}]$ 间，其十进制表示（无前导零）能被 $\mathbf{R}$ 匹配？

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组包含两行。第一行为两个正整数 $\mathbf{A}$ 和 $\mathbf{B}$，表示所关心的整数区间（闭区间）。第二行为一个仅由 `0123456789()|*` 组成的字符串 $\mathbf{R}$，保证其为合法正则表达式（如上所述）。

对于每组测试用例，输出一行 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为区间 $[\mathbf{A}, \mathbf{B}]$ 内能被正则表达式 $\mathbf{R}$ 匹配的整数个数。

**样例解释** 注意，样例 5 至 8 不会出现在小数据集中。 在样例 1 中，区间内匹配的数字为 $1, 10, 100, 1000$。 在样例 2 中，区间内匹配的数字为 $379009$。 在样例 3 中，区间内匹配的数字为 $12, 34, 1212, 1234, 3434$。 在样例 4 中，没有匹配的数字。 在样例 5 中，区间内匹配的数字为 $1, 10, 11, 100$。 在样例 6 中，区间内匹配的数字为 $23, 45$。 在样例 7 中，区间内的任意数字都能被匹配。 在样例 8 中，区间内匹配的数字为 $1, 19, 156, 179, 189, 199$。 **限制条件** - $1 \leqslant \mathbf{T} \leqslant 100$。 - $1 \leqslant \mathbf{A} \leqslant \mathbf{B} \leqslant 10^{18}$。 - $1 \leqslant \mathbf{R}$ 的长度 $\leqslant 30$。 **小数据集（15 分，测试集 1 - 可见）** - $\mathbf{R}$ 不包含 | 字符。 **大数据集（15 分，测试集 2 - 隐藏）** - 无其他限制。 翻译由 GPT4.1 完成。