CF2249E2 String (Hard 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$ 视为字符串，你的任务是在字符串 $s_l s_{l+1} \ldots s_r$ 中，计算 $t$ 出现的次数。 对于数值大于等于十的数字，使用大写和小写字母表示。具体而言，大写字母 $\{\mathtt{A, B, \ldots, Z}\}$ 分别代表十进制 $\{10, 11, \ldots, 35\}$，小写字母 $\{\mathtt{a, b, \ldots, z}\}$ 分别代表十进制 $\{36, 37, \ldots, 61\}$。

输入的第一行包含两个整数 $k$ 和 $q$（$2\le k\le 62$，$1\le q\le 10^4$），分别表示进制和询问个数。 接下来每个询问包含两行。第一行包含三个整数 $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,B,\ldots,Z,a,b,\ldots,z}\}$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^6$。

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

记子串 $s_ls_{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$ 中分别为 $s[6;8]$ 和 $s[12;14]$。而 $t=\mathtt{01}$ 出现了 $3$ 次，对应 $s$ 中 $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 翻译