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

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 values given in the constraints, . The operation then becomes a simple range sum query.

Time Complexity:

## Comments

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

All possible values of are prime, so .