/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
T 個のテストケースについて、数字のみからなる文字列 S と正整数 L,R が与えられるので、以下の問題を解いてください。
正整数 x に対して f(x)= ( x を ( 先頭に 0 を含まないように ) 書き下した文字列の連続部分列のうち 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
この入力には 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 となることに注意してください。
Score : 500 points
Problem Statement
You are given a string S consisting of digits and positive integers L and R for each of T test cases. Solve the following problem.
For a positive integer x, let us define f(x) as the number of contiguous substrings of the decimal representation of x (without leading zeros) that equal S.
For instance, if S= 22, we have f(122) = 1, f(123) = 0, f(226) = 1, and f(222) = 2.
Find \displaystyle \sum_{k=L}^{R} f(k).
Constraints
- 1 \le T \le 1000
- S is a string consisting of digits whose length is between 1 and 16, inclusive.
- L and R are integers satisfying 1 \le L \le R < 10^{16}.
Input
The input is given from Standard Input in the following format, where \rm{case}_i denotes the i-th test case:
T
\rm{case}_{1}
\rm{case}_{2}
\vdots
\rm{case}_{\it{T}}
Each test case is in the following format:
S L R
Output
Print T lines in total.
The i-th line should contain an integer representing the answer to the i-th test case.
Sample Input 1
6 22 23 234 0295 295 295 0 1 9999999999999999 2718 998244353 9982443530000000 869120 1234567890123456 2345678901234567 2023032520230325 1 9999999999999999
Sample Output 1
12 0 14888888888888889 12982260572545 10987664021 1
This input contains six test cases.
- In the first test case, S=
22, L=23, R=234.- f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1.
- f(222)=2.
- Thus, the answer is 12.
- In the second test case, S=
0295, L=295, R=295.- Note that f(295)=0.