CF2249E1 String (Easy Version)

这是这个问题的简单版本。不同版本的区别在于本题中 $k$ 和 $q$ 的约束条件更小。你只有在解决了所有版本后才能进行 Hack。 定义 $\mathrm{popcount}_k(m)$ 为 $m$ 在 $k$ 进制下所有数位之和。 定义一个无限长度的 $k$ 进制整数 $s=\overline{s_1s_2\cdots}$，其中第 $i$ 位数字 $s_i = (\mathrm{popcount}_k(i)\bmod k)$。 给定 $q$ 组询问。每组询问包含三个十进制整数 $l$、$r$、$n$，以及一个有 $n$ 位的 $k$ 进制整数 $t$（注意，$t$ 可能包含前导零）。将 $t$ 看作一个字符串，你需要求 $t$ 在字符串 $s_l s_{l+1} \ldots s_r$ 中出现的次数。 对于大于等于十进制 $10$ 的数字，使用大小写字母来表示。具体地，大写字母 $\{\mathtt{A, B,\ldots,Z}\}$ 分别表示十进制值 $\{10, 11,\ldots,35\}$，小写字母 $\{\mathtt{a, b,\ldots,z}\}$ 分别表示十进制值 $\{36, 37,\ldots,61\}$。

输入的第一行包含两个整数 $k$ 和 $q$（$2\le k\le 10$，$1\le q\le 1000$），表示进制和询问数量。 每组询问包含两行。第一行包含三个整数 $l$、$r$、$n$（$1\le l\le r\le 10^{17}$，$1\le n\le 2\cdot 10^6$）。 第二行包含一个有 $n$ 位的 $k$ 进制整数 $t$（$t_i\in\{\mathtt{0,1,\ldots,9,A,\ldots,Z,a,\ldots,z}\}$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^6$。

对于每个询问，输出一个整数，表示答案。

记字符串 $s_l s_{l+1} \ldots s_r$ 为 $s[l;r]$。 在第一个样例中，$k=3$，$s=\mathtt{12120201120201012201120012\ldots}$，$s[5;17]=\mathtt{0201120201012}$，$t=\mathtt{201}$ 在 $s[5;17]$ 中总共出现 $2$ 次，分别在 $s[6;8]$ 和 $s[12;14]$。而 $t=\mathtt{01}$ 出现了 $3$ 次，位置为 $s[7;8]$、$s[13;14]$ 和 $s[15;16]$。 在第二个样例中，$k=10$，$s[1;20]=\mathtt{12345678912345678902}$，$t=\mathtt{123456789}$ 在 $s[1;20]$ 中总共出现 $2$ 次。 由 ChatGPT 5 翻译