나머지 합

면접 대비

시간 제한1초메모리 제한256 MB

요약

합이 M으로 나누어떨어지는 연속 구간 개수를 누적합 나머지 빈도로 셉니다.

문제

길이가 $N$ 인 수열 $A_1, A_2, \dots, A_N$ 이 주어진다. 연속한 구간의 합이 $M$ 으로 나누어떨어지는 구간의 개수를 구한다.

구간은 $1 \le i \le j \le N$ 을 만족하는 쌍 $(i, j)$ 로 나타내고, $A_i$ 부터 $A_j$ 까지를 포함한다. $i$ 나 $j$ 중 하나라도 다르면 서로 다른 구간으로 센다.

첫째 줄에 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. ( $1 \le N \le 10^6$ , $2 \le M \le 10^3$ )

둘째 줄에 수열을 이루는 $N$ 개의 수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어진다. ( $0 \le A_i \le 10^9$ )

조건을 만족하는 구간의 개수를 첫째 줄에 출력한다.