← 返回题目列表

AtCoder · abc146_e

E. 总和的 Rem 为 Num

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

分数: 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