CF216E Martian Luck

你知道火星人使用 $k$ 进制的数字系统。数字 $b$（$0 \leq b < k$）被认为是幸运数字，因为火星人与地球人的首次接触发生在火星纪年 $b$ 年。 一个数 $x$ 的数字根 $d(x)$ 是一个一位数，得到方法是将 $x$ 的所有数字递归相加。这里的“递归”指的是：如果第一次相加的结果不是一位数，则将结果的所有数字继续相加，如此反复，直到得到一个一位数为止。 例如，$d(3504_{7})=d((3+5+0+4)_{7})=d(15_{7})=d((1+5)_{7})=d(6_{7})=6_{7}$。在这个例子中，所有计算均在 $7$ 进制下进行。 如果一个数的数字根等于 $b$，火星人也称这个数为“幸运数字”。 你有一个长度为 $n$ 的字符串 $s$，其中每个字符是 $k$ 进制的一位数字。你的任务是计算，有多少个不同的子串是幸运数字。数字前导零是允许的。 注意：字符串 $s[i...j]$ 表示字符串 $s=a_1a_2...a_n$ 的从第 $i$ 个到第 $j$ 个子串（$1 \leq i \leq j \leq n$），也就是 $a_ia_{i+1}...a_j$。如果 $i_1 \neq i_2$ 或 $j_1 \neq j_2$，则 $s[i_1...j_1]$ 和 $s[i_2...j_2]$ 被认为是不同的子串。

第一行包含三个整数 $k$、$b$、$n$（$2 \leq k \leq 10^{9}$，$0 \leq b < k$，$1 \leq n \leq 10^5$）。 第二行包含长度为 $n$ 的字符串 $s$，由 $n$ 个用空格分隔的整数组成，表示 $k$ 进制下的每一位数字，第 $i$ 个数字为 $a_i$（$0 \leq a_i < k$）——字符串 $s$ 的第 $i$ 位。

输出一个整数，表示幸运数字子串的个数。 请不要在 C++ 语言中使用 %lld 格式读取或输出 64 位整数。推荐使用 cin、cout 或 %I64d 格式。

在第一个样例中，以下子串的数字根等于给定值：$s[1...2] = "3\ 2"$，$s[1...3] = "3\ 2\ 0"$，$s[3...4] = "0\ 5"$，$s[4...4] = "5"$，以及 $s[2...6] = "2\ 0\ 5\ 6\ 1"$。 由 ChatGPT 5 翻译