DMOPC '17 Contest 1 P2 - Sharing Crayons

View as PDF

Submit solution



Points:7 (partial)
Time limit:2.0s
Memory limit:64M
Authors:

Problem type

Mimi is helping out at a daycare! There are M children and N boxes of crayons in a row, the i^\text{th} of which has c_i crayons. Mimi will choose a single contiguous section of crayon boxes to give to the children. In order to be fair, she also wants the total number of crayons in the subarray she chooses to be divisible by M so that it can be split equally. How many ways can she do this?

Constraints

For all subtasks, 1 \le c_i \le 10^9.

Subtask 1 [20%]

1 \le N \le 100
1 \le M \le 10^9

Subtask 2 [20%]

1 \le N \le 2\ 000
1 \le M \le 10^6

Subtask 3 [40%]

1 \le N \le 10^5
1 \le M \le 10^6

Subtask 4 [20%]

1 \le N \le 10^5
1 \le M \le 10^9

Input Specification

The first line will have two space separated integers, N and M.
The second line will have N space separated integers, c_1, c_2, \ldots, c_N.

Output Specification

A single integer, the number of subarrays which have a total which is a multiple of M. This number may overflow 32-bit numbers.

Sample Input

5 6
3 5 9 6 10

Sample Output

2

Explanation for Sample

The two subarrays with a sum divisible by 6 are [6] and [5, 9, 6, 10].


Comments

There are no comments at the moment.