Editorial for LKP '18 Contest 2 P2 - Secret Signal

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

Let $P_i = \sum_{j=1}^i a_i$ ~P_i = \sum_{j=1}^i a_i~.

Notice that the sum of a subarray $a[l, r]$ ~a[l, r]~ will be divisible by $K$ ~K~ if $P_r \bmod K \equiv P_{l-1} \bmod K$ ~P_r \bmod K \equiv P_{l-1} \bmod K~. Thus we can store a counter array $C$ ~C~ of size $K$ ~K~ such that the $i$ ~i~th entry is the number of prefix sums that are congruent to $i$ ~i~ mod $K$ ~K~. Thus we can just loop through $a$ ~a~, and add $C[a_i]$ ~C[a_i]~ to our answer, and then increment it by one.

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.