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.

By Jerry Zhang (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)


  • 0
    4fecta  commented on July 28, 2019, 2:38 p.m.

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

    • -3
      verybadallen  commented on July 29, 2019, 12:12 p.m.

      bruh why u stupid

      • -6
        zey_zey  commented on July 29, 2019, 12:23 p.m.

        This comment is hidden due to too much negative feedback. Click here to view it.

    • 3
      discoverMe  commented on July 28, 2019, 6:19 p.m. edited

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