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 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)

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. ← edit 3

      All possible values of M are prime, so a^M \equiv a \pmod M.