substr = S

题目描述

你将得到一个由数字组成的字符串 $S$ 以及对每个 $T$ 个测试用例给出的正整数 $L$ 和 $R$。解决以下问题。 对于正整数 $x$，令 $f(x)$ 表示在 $x$ 的十进制表示（不含前导零）的所有连续子字符串中等于 $S$ 的个数。 例如，如果 $S=$ $22$，我们有 $f(122) = 1$, $f(123) = 0$, $f(226) = 1$, 和 $f(222) = 2$。 求 $\displaystyle \sum_{k=L}^{R} f(k)$。

输入格式

输入按以下格式从标准输入给出，其中 $\rm{case}_i$ 表示第 $i$ 个测试用例： $T$ $\rm{case}_{1}$ $\rm{case}_{2}$ $\vdots$ $\rm{case}_{\it{T}}$

每个测试用例格式如下： $S$ $L$ $R$

输出格式

共打印 $T$ 行。
第 $i$ 行应包含一个整数，表示第 $i$ 个测试用例的答案。

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

12
0
14888888888888889
12982260572545
10987664021
1

提示

$1 \le T \le 1000$ $S$ 是由数字组成的字符串，长度在 $1$ 到 $16$（含）之间。 $L$ 和 $R$ 为满足 1 \le L \le R < 10^{16} 的整数。该输入包含六个测试用例。

在第一个测试用例中，$S=$ $22$, $L=23$, $R=234$。 $f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1$。 $f(222)=2$。 因此，答案是 $12$。

在第二个测试用例中，$S=$ $0295$, $L=295$, $R=295$。 注意 $f(295)=0$.

标签: AtCoder|abc295F

来源

AtCoder|abc295F