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.
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 for any
The number of good subsequences is the sum of dp[i] 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.