## Problem statement

You're given a sequence , of positive integers and an integer . The task is to return the number of consecutive subsequences of the input sequence whose sum of elements is divisible by . We call these subsequences **good**. The full problem statement is here.

## Solution

The first observation is that the number of good subsequences is not greater than which fits in 64-bit integer. I used a simple dynamic programming solution here. Let:

number of subsequences ending in A[i] whose sum of elements divided by gives a rest . It's worth to mention, that , because .

It's easy to compute for any using and , more precisely:

and

and for any

The number of good subsequences is the sum of dp[i][0] for every .

The last observation is that we need only table when computing , so there is no need to store the whole table.

The time complexity of that solution is , but one testfile contains at most 20 test cases, so in the worst case it makes about operations per testfile which is quite big. Fortunately, as I thought, the time limit is not a problem for that solution, because of average test files.