AT_abc295_f [ABC295F] substr = S

题目描述

对于 $T$ 个测试用例，给定一个仅由数字组成的字符串 $S$，以及正整数 $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}_T$

每个测试用例格式如下：

$S$ $L$ $R$

输出格式

请输出共 $T$ 行。
第 $i$ 行输出第 $i$ 个测试用例的答案，结果为整数。

输入输出样例 #1

输入 #1

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

输出 #1

12
0
14888888888888889
12982260572545
10987664021
1

说明/提示

限制

• $1 \leq T \leq 1000$
• $S$ 是长度在 $1$ 到 $16$ 之间的仅由数字组成的字符串
• $L,R$ 满足 $1 \leq L \leq R < 10^{16}$

样例解释 1

该输入包含 $6$ 个测试用例。

• 第 $1$ 个用例为 $S=22$，$L=23$，$R=234$。
  • $f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1$
  • $f(222)=2$
  • 因此，该用例的答案为 $12$。
• 第 $2$ 个用例为 $S=0295$，$L=295$，$R=295$。
  • 注意 $f(295)=0$。

由 ChatGPT 4.1 翻译