← 返回题目列表

Codeforces · 776/C

C. 莫莉的化学品

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

莫莉·胡珀 (Molly Hooper) 有 n 种不同种类的化学品排列成一行。每种化学物质都有一个情感值,其中第 i 个具有情感值 ai。

莫莉希望夏洛克爱上她。为此,她打算将一段连续的化学物质混合在一起,制成一种爱情药水,其总感情值为 k 的非负整数次方。化学品连续段的总影响值是该段中每种化学品影响值的总和。

帮助她找到此类片段的总数。

输入

输入的第一行包含两个整数,n和k,化学品的数量和数量,使得总影响值是该数量k的非负幂。 (1 ≤ n ≤ 105,1 ≤ |k| ≤ 10)。

下一行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 化学品的影响值。

输出

输出一个整数——有效段的数量。

示例

输入 #1

4 2
2 2 2 2

输出 #1

8

输入 #2

4 -3
3 -6 -3 12

输出 #2

3

注意

请记住 k0 = 1。

在第一个示例中,Molly 可以获得以下不同的情感值:

- 2:段[1, 1]、[2, 2]、[3, 3]、[4, 4];
- 4:段[1, 2]、[2, 3]、[3, 4];
- 6:段[1, 3],[2, 4];
- 8:段 [1, 4]。

其中,2、4 和 8 是 k = 2 的幂。因此,答案是 8。

在第二个示例中,Molly 可以选择段 [1, 2]、[3, 3]、[3, 4]。