Escrito por Leonardo Paes
Conhecimento prévio necessário:
A ideia principal para resolvermos esse problema é que a soma de valores de um intervalo (subvetor) é a subtração de duas somas de prefixos do vetor original. Por exemplo: Dado o subvetor com índices de $$l$$ a $$r$$ a sua soma é $$pref[r] – pref[l-1]$$, onde $$pref[]$$ é o vetor das somas de prefixos.
Ao fixarmos o $$r$$, o final de um certo subvetor, basicamente queremos saber a quantidade de $$l$$ tal que $$l \leq r$$ e $$pref[r] – pref[l-1] \equiv 0 \;(mod \;n)$$, e isso é o mesmo que: $$pref[r] \equiv pref[l-1] \;(mod \;n)$$.
Para encontrarmos essa quantidade de $$l$$ para cada $$r$$, basta utilizarmos um $$map$$ de frequências, que diz a quantidade de prefixos anteriores a $$r$$ com soma congruente a um certo valor módulo $$n$$.
Confira o código abaixo para melhor entendimento: