分数: 500 点
问题陈述
给你一个字符串 S 由数字和正整数组成 L 和 R 对于每个 T 测试用例。解决以下问题。
对于正整数 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).
约束
- 1 \le T \le 1000
- S 是由数字组成的字符串,其长度介于 1 和 16,包括在内。
- L 和 R 是满足以下条件的整数 1 \le L \le R < 10^{16}.
输入
输入由标准输入按以下格式给出,其中 \rm{case}_i 表示 i-第一个测试用例:
T
\rm{case}_{1}
\rm{case}_{2}
\vdots
\rm{case}_{\it{T}}
每个测试用例均采用以下格式: 总共
S L R
输出
打印 T 行。
的 i- 第行应包含一个整数,表示问题的答案 i- 第一个测试用例。
示例输入 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
此输入包含六个测试用例。
- 在第一个测试用例中, 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.