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)


Comments


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

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


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

      bruh why u stupid


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

        f


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

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