10954: 小光的难题
[Creator : ]
Description
小光现在有一个长度为 $n$ 的序列,他想从中间挑一串连续的子序列,使得他们的和与 $m$ 取余为 $0$。
小光发现,这样情况太多了,数都数不过来。
于是小光想请你帮忙解决这个问题。
小光发现,这样情况太多了,数都数不过来。
于是小光想请你帮忙解决这个问题。
Input
输入有两行。
第一行包括两个数字 $n,m\ (1 \leq n,m \leq 2\times 10^5)$。
第二行包括 $n$ 个数字,每个数都是正整数且小于 $10^7$。
第一行包括两个数字 $n,m\ (1 \leq n,m \leq 2\times 10^5)$。
第二行包括 $n$ 个数字,每个数都是正整数且小于 $10^7$。
Output
输出一个整数,表示答案。
Sample 1 Input
5 3
1 2 3 4 5
Sample 1 Output
7
符合条件的子序列有 7 个。具体如下
{1,2},{1,2,3},{1,2,4,4,5}
{2,3,4},
{3},{3,4,5}
{4,5}
{1,2},{1,2,3},{1,2,4,4,5}
{2,3,4},
{3},{3,4,5}
{4,5}
Sample 2 Input
10 17
17 17 17 17 17 17 17 17 17 17
Sample 2 Output
55
Sample 3 Input
14 13
8 15 13 18 19 10 6 5 14 12 3 12 19 1
Sample 3 Output
5