Editorial for DMOPC '17 Contest 1 P2 - Sharing Crayons
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask, we can loop through all subarrays and find their sum, and count how many are divisible by .
Time Complexity:
For the second subtask, we can iterate through all subarrays and find their sum using a prefix sum array, and count how many are divisible by .
Time Complexity:
Let .
For the third subtask, notice that the sum of a subarray will be divisible by
if
. Thus we can store a counter array
of size
such that the
th entry is the number of prefix sums that are congruent to
mod
. Thus we can just loop through
, and add
to our answer, and then increment it by one.
Time Complexity:
For the fourth subtask, we can replace the counter array with a map data structure, as an array of size will MLE.
Time Complexity:
Extra Challenge: Can you solve this problem without using a map data structure?
Comments