Editorial for DMOPC '15 Contest 1 P6 - Lelei and Contest

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: cheesecake

The simplest solution here is segment tree with lazy propagation. Operation 1 is the classical range update. Operation 2 requires a little more mathematical insight. Using Fermat's Little Theorem and binomial expansion via Pascal's Triangle, we can see that for all $M$ ~M~ values given in the constraints, $(a_1^M + a_2^M + \dots + a_n^M) \bmod M \equiv (a_1 + a_2 + \dots + a_n) \bmod M$ . The operation then becomes a simple range sum query.

Time Complexity: $\mathcal{O}((N+Q) \log N)$ ~\mathcal{O}((N+Q) \log N)~

Comments

3

4fecta commented on July 28, 2019, 6:38 p.m.

Can someone clarify how one can use binomial expansion to prove the above identity?

5

discoverMe commented on July 28, 2019, 10:19 p.m. ← edited →

All possible values of $M$ ~M~ are prime, so $a^M=a\mod M$ ~a^M=a\mod M~