AT_abc295_f.[ABC295F] substr = S

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于 $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

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页