## Editorial for Yet Another Contest 5 P1 - Number Pyramid

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

#### Subtask 1

We should try to make as large as possible, so we should set it to . Since mod , we may calculate mod .

**Time complexity:**

#### Subtask 2

We should try to make as large as possible, so we should set them all to . We now need to choose the value of such that . It suffices to brute force over all possible values of , constructing the entire pyramid in order to check if .

**Time complexity:**

#### Subtask 3

Again, set to . Set to , and construct the pyramid. Notice that if we increment by , then will also increase by , since only the rightmost values in each row of the pyramid are affected. This allows us to easily calculate the number of times we must increment in order for to equal .

**Time complexity:**

#### Subtask 4

Again, set to . Observe that the pyramid resembles that of Pascal's triangle. In fact, if we were to multiply each number in row by the number in the corresponding position in Pascal's triangle, then the sum of those numbers taken modulo would equal . Formally, mod . This can be observed by considering each number in the pyramid algebraically as the sum of multiples of values in row .

If we were to set all numbers in row to , then would equal mod . This is because the sum of each row in Pascal's triangle is a power of two. This can also be proven using the binomial theorem to show that mod mod mod . Applying the idea from subtask , we see that we should increment times. Thus, we should 'correct' the value of by setting it to mod .

**Time complexity:**

## Comments