CF1729F Kirei and the Linear Function

给定一个长度为 $n$ 的十进制数字字符串 $s$（仅包含 0-9）。 子串是字符串中一段连续的字符。该字符串的子串由一对下标定义——即其左端点和右端点。因此，每一对下标 $(l, r)$，其中 $1 \le l \le r \le n$，都对应于字符串 $s$ 的一个子串。我们将该子串的数值定义为 $v(l, r)$（允许前导零）。 例如，如果 $n=7$，$s=$"1003004"，则 $v(1,3)=100$，$v(2,3)=0$，$v(2,7)=3004$。 现给定 $n$、$s$ 和一个整数 $w$（$1 \le w < n$）。 你需要处理 $m$ 个询问，每个询问由三个数 $l_i, r_i, k_i$（$1 \le l_i \le r_i \le n; 0 \le k_i \le 8$）描述。 对于第 $i$ 个询问，答案是这样一对长度为 $w$ 的子串，如果我们记它们为 $(L_1, L_1+w-1)$ 和 $(L_2, L_2+w-1)$，则需满足： - $L_1 \ne L_2$，即这两个子串不同； - 数值 $v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1)$ 除以 $9$ 的余数等于 $k_i$。 如果有多组满足条件的子串对，优先选择 $L_1$ 最小的那组；若 $L_1$ 相同，则选择 $L_2$ 最小的那组。 注意，答案可能不存在。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示输入的测试用例数。 每个测试用例的第一行包含一个仅由数字 0-9 组成的字符串 $s$，长度为 $n$（$2 \le n \le 2 \cdot 10^5$）。 第二行包含两个整数 $w, m$（$1 \le w < n, 1 \le m \le 2 \cdot 10^5$），其中 $n$ 是字符串 $s$ 的长度。$w$ 表示所需子串的长度，$m$ 表示需要处理的询问数。 接下来的 $m$ 行，每行包含三个整数 $l_i, r_i, k_i$（$1 \le l_i \le r_i \le n$，$0 \le k_i \le 8$），表示第 $i$ 个询问的参数。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个询问，输出一行： - 所需子串的左端点：$L_1$ 和 $L_2$； - 如果无解，则输出 $-1\ -1$。 如果有多组解，优先输出 $L_1$ 最小的，若 $L_1$ 相同，则输出 $L_2$ 最小的。

考虑示例输入的第一个测试用例。在该测试用例中，$n=7$，$s=$"1003004"，$w=4$，有一个询问 $l_1=1$，$r_1=2$，$k_1=1$。注意 $v(1,2)=10$。我们需要找到一对长度为 $4$ 的子串，使得 $v(L_1, L_1+3)\cdot10+v(L_2,L_2+3)$ 除以 $9$ 的余数为 $k_1=1$。取 $L_1=2, L_2=4$ 满足所有条件：$v(L_1, L_1+w-1)=v(2,5)=30$，$v(L_2, L_2+w-1)=v(4,7)=3004$。确实，$30\cdot10+3004=3304$，其除以 $9$ 的余数为 $1$。可以证明 $L_1=2$ 是最小可能值，且 $L_2=4$ 是在 $L_1=2$ 时最小的。 由 ChatGPT 4.1 翻译