← 返回题目列表

Codeforces · 216/E

E. 火星运气

中文机器翻译题面 查看原题

你知道火星人使用以 k 为基数的数字系统。数字 b (0 ≤ b < k) 被认为是幸运的,因为火星人和地球人之间的第一次接触发生在 b 年(按火星年表)。

数字 x 的数字根 d(x) 是由单个数字组成的数字,是对数字 x 的所有数字进行级联求和后得到的结果。 “级联”一词的意思是,如果第一次求和得到一个由多个数字组成的数字,那么我们将再次对所有数字求和,直到得到一位数字。

例如,d(35047) = d((3 + 5 + 0 + 4)7) = d(157) = d((1 + 5)7) = d(67) = 67。在此示例中,计算以 7 进制表示法执行。

如果一个数字的数字根等于b,火星人也称这个数字为幸运数字。

您有字符串 s,它由 k 基表示法系统中的 n 位数字组成。你的任务是找出给定字符串中有多少个不同的子串是幸运数字。数字中允许使用前导零。

请注意,字符串 s = a1a2... an (1 ≤ i ≤ j ≤ n) 的子串 s[i... j] 是字符串 aiai + 1... aj。如果 i1 ≠ i2 或 j1 ≠ j2,则字符串 s 的两个子串 s[i1...j1] 和 s[i2...j2] 不同。

输入

第一行包含三个整数 k、b 和 n (2 ≤ k ≤ 109, 0 ≤ b < k, 1 ≤ n ≤ 105)。

第二行包含字符串 s,作为 n 个整数的序列,表示 k 基表示法中的数字:第 i 个整数等于 ai (0 ≤ ai < k) — 字符串 s 的第 i 个数字。行中的数字以空格分隔。

输出

打印一个整数——幸运数字的子串数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

10 5 6
3 2 0 5 6 1

输出 #1

5

输入 #2

7 6 4
3 5 0 4

输出 #2

1

输入 #3

257 0 3
0 0 256

输出 #3

3

注意

在第一个示例中,以下子字符串具有所寻找的数字根: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"。