substr = S

AtCoder

IDabc295_f

Time4000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

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$ [samples]

对于每个测试用例，给定一个由数字组成的字符串 $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)$。 ## Constraints * $1 \le T \le 1000$ * $S$ 是由数字组成的字符串，长度在 $1$ 到 $16$ 之间（含）。 * $L$ 和 $R$ 是满足 $1 \le L \le R < 10^{16}$ 的整数。 ## Input 输入从标准输入按以下格式给出，其中 $\rm{case}_i$ 表示第 $i$ 个测试用例： $T$ $\rm{case}_{1}$ $\rm{case}_{2}$ $\vdots$ $\rm{case}_{\it{T}}$ 每个测试用例的格式如下： $S$ $L$ $R$ [samples]

Samples

Input #1

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

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$.

API Response (JSON)

{
  "problem": {
    "name": "substr = S",
    "description": {
      "content": "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 numbe",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc295_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\nFor a positive integer $x$, let us define $f(x)$ as the numbe...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "对于每个测试用例，给定一个由数字组成的字符串 $S$ 以及两个正整数 $L$ 和 $R$。请解决以下问题：\n对于正整数 $x$，定义 $f(x)$ 为 $x$ 的十进制表示（不含前导零）中等于 $S$ 的连续子串的个数。\n例如，若 $S=$ `22`，则有 $f(122) = 1$，$f(123) = 0$，$f(226) = 1$，$f(222) = 2$。\n求 $\\displaystyle \\...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments