Editorial for An Animal Contest 6 P3 - OAC
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's denote the array as and the length to be .
Observe that if the sum in the range is divisible by its length, then every element it contains must be equal to every other element.
With this in mind, we can solve this problem using the two-pointers technique.
Let's try to extend our observation from subtask 1. First note that if the sum of the subarray in the range is divisible by its length then we can write as for some .
Next, let's prove that always holds regardless of what subarray we choose. This is because we can use the fact that to prove that:
With this in mind we can brute force all possible values of and for each of them check the number of subarrays whose sum can be written as .
For a given this is equivalent for finding the number of pairs such that:
Which can be rewritten as:
With this in mind, we can calculate the number of valid pairs for a given with a frequency table and a prefix sum array to quickly compute values of .