String (Easy Version)AI (CI翻译)
This is the easy version of the problem. The difference between the versions is that in this version, the constraints on $k$ and $q$ are smaller. You can hack only if you solved all versions of this problem.
Define $\mathrm{popcount}_k(m)$ as the sum of all digits of $m$ in base $k$.
Define a base-$k$ integer $s=\overline{s_1s_2\cdots}$ of infinite length, where the $i$-th digit of $s$ is $s_i=(\mathrm{popcount}_k(i) \bmod k)$.
There are $q$ queries. Each query consists of three integers $l$, $r$, and $n$ (all of them are given in decimal form), as well as a base-$k$ integer $t$ with $n$ digits. Note that $t$ may have leading zeros. Consider $t$ as a string, and your task is to find the number of occurrences of $t$ in the string $s_ls_{l+1}\ldots s_r$.
For digits greater than or equal to decimal $\mathtt{10}$, uppercase and lowercase letters are used. Specifically, the uppercase letters $\{\mathtt{A, B,\ldots,Z}\}$ represent the decimal values $\{\mathtt{10, 11,\ldots,35}\}$, and the lowercase letters $\{\mathtt{a, b,\ldots,z}\}$ represent the decimal values $\{\mathtt{36, 37,\ldots,61}\}$.
Input
The first line of the input contains two integers $k$ and $q$ ($2\le k\le 10$, $1\le q\le 1000$) — the base and the number of queries.
Each query contains two lines. The first line contains the three integers $l$, $r$, and $n$ ($1\le l\le r\le 10^{17}$, $1\le n\le 2\cdot 10^6$).
The second line contains the base-$k$ integer $t$ with $n$ digits ($t_i\in\{\mathtt{0,1,\ldots,9,A,B,\ldots,Z,a,b,\ldots,z}\}$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^6$.
Output
For each query, output a single integer — the answer to the query.
Note
Denote the string $s_ls_{l+1}\ldots s_r$ as $s[l;r]$.
In the first example, $k = 3$, $s = \mathtt{12120201120201012201120012\ldots}$, $s[5;17] = \mathtt{0201120201012}$, and $t = \mathtt{201}$ appears a total of $2$ times in $s[5; 17]$. Their indices in the string $s$ are $s[6; 8]$ and $s[12; 14]$. And $t = \mathtt{01}$ appears $3$ times. Their indices in the string $s$ are $s[7;8]$, $s[13;14]$, and $s[15;16]$.
For the second example, $k=10$, $s[1;20] = \mathtt{12345678912345678902}$, and $t = \mathtt{123456789}$ appears a total of $2$ times in $s[1;20]$.
{"titleZh":"字符串（简单版本）","bodyZh":"这是本题的简单版本。不同版本之间的区别在于，本版本中 $k$ 和 $q$ 的约束更小。只有解决了本题的所有版本后才能进行 hack。\n\n定义 $\\mathrm{popcount}_k(m)$ 为 $m$ 在 $k$ 进制下的所有数位之和。\n\n定义一个无限长度的 $k$ 进制整数 $s=\\overline{s_1s_2\\cdots}$，其中 $s$ 的第 $i$ 位为 $s_i=(\\mathrm{popcount}_k(i) \\bmod k)$。\n\n现在有 $q$ 个询问。每个询问由三个整数 $l$、$r$ 和 $n$ 组成（它们均以十进制形式给出），以及一个包含 $n$ 位的 $k$ 进制整数 $t$。注意，$t$ 可能包含前导零。将 $t$ 视为一个字符串，你需要求出 $t$ 在字符串 $s_ls_{l+1}\\ldots s_r$ 中出现的次数。\n\n对于大于或等于十进制 $\mathtt{10}$ 的数位，使用大写和小写字母表示。具体来说，大写字母集合 $\\{\\mathtt{A, B,\\ldots,Z}\\}$ 分别表示十进制数值 $\\{\\mathtt{10, 11,\\ldots,35}\\}$，小写字母集合 $\\{\\mathtt{a, b,\\ldots,z}\\}$ 分别表示十进制数值 $\\{\\mathtt{36, 37,\\ldots,61}\\}$。\n\n## 输入格式\n\n输入的第一行包含两个整数 $k$ 和 $q$（$2\\le k\\le 10$，$1\\le q\\le 1000$），分别表示进制和询问数量。\n\n每个询问包含两行。第一行包含三个整数 $l$、$r$ 和 $n$（$1\\le l\\le r\\le 10^{17}$，$1\\le n\\le 2\\cdot 10^6$）。\n\n第二行包含一个有 $n$ 位的 $k$ 进制整数 $t$（$t_i\\in\\{\\mathtt{0,1,\\ldots,9,A,B,\\ldots,Z,a,b,\\ldots,z}\\}$）。\n\n保证所有询问中的 $n$ 之和不超过 $2 \\cdot 10^6$。\n\n## 输出格式\n\n对于每个询问，输出一个整数，表示询问的答案。\n\n## 说明\n\n将字符串 $s_ls_{l+1}\\ldots s_r$ 记作 $s[l;r]$。\n\n在第一个样例中，$k = 3$，$s = \\mathtt{12120201120201012201120012\\ldots}$，$s[5;17] = \\mathtt{0201120201012}$，且 $t = \\mathtt{201}$ 在 $s[5; 17]$ 中共出现 $2$ 次。它们在字符串 $s$ 中的下标区间为 $s[6; 8]$ 和 $s[12; 14]$。而 $t = \\mathtt{01}$ 共出现 $3$ 次，它们在字符串 $s$ 中的下标区间为 $s[7;8]$、$s[13;14]$ 和 $s[15;16]$。\n\n在第二个样例中，$k=10$，$s[1;20] = \\mathtt{12345678912345678902}$，且 $t = \\mathtt{123456789}$ 在 $s[1;20]$ 中共出现 $2$ 次。"}AI (CI翻译)
样例
3 4
5 17 3
201
5 17 2
01
1239 1231231209 5
01201
123002 231203 4
1202
2
3
21046666
8325
10 3
1 20 9
123456789
15 20332 3
678
1234 56789 2
01
2
1625
5000
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。