分数: 500 点
问题陈述
给出了一系列 N 正整数 A_1, A_2, \ldots, A_N,和一个正整数 K.
查找非空连续子序列的数量 A 使得其元素之和除以的余数 K 等于其元素的数量。如果两个子序列取自不同的位置,即使它们是相同的序列,我们也认为它们是不同的。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \cdots A_N
输出
打印满足条件的子序列的数量。
示例输入 1
5 4 1 4 2 3 5
示例输出 1
4
四个序列满足条件: (1), (4,2), (1,4,2),和 (5).
示例输入 2
8 4 4 2 4 2 4 2 4 2
示例输出 2
7
(4,2) 被计数四次,并且 (2,4) 计数了 3 次。
示例输入 3
10 7 14 15 92 65 35 89 79 32 38 46
示例输出 3
8