← 返回题目列表

AtCoder · abc295_f

I. 子字符串 = S

中文机器翻译题面 查看原题

分数: 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.