## Editorial for Angie and Functions

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

#### Subtasks 1 and 2

Subtasks 1 and 2 were intended to reward brute force solutions.

Time Complexity:

Query Complexity:

#### Subtask 3

##### Official Solution

Observe that the difference of an degree polynomial is equivalent to its derivative.

First, query any adjacent values.

Now, calculate the difference of the original function, this can be done in time using brute force. Then, find the function for the derivative using the power rule and finally solve for the first coefficient () using algebra. Note that modular inverse is required for this part.

Lastly, subtract from all of the queried values, this turns into . As the polynomial has now been reduced to an degree polynomial the above process can be repeated to find .

Time Complexity:

Query Complexity:

##### Alternative Solution

Observe that any values can be queried to set up a system of equations to solve for the coefficients. The coefficients can be found using Gaussian elimination in .

Time Complexity:

Query Complexity:

#### Subtask 4

##### Official Solution

To get the full solution, simply optimize the method from the previous subtask. Observe that the difference of a function follows a regular pattern, allowing the difference to be calculated in time. This brings the overall complexity down to .

The pattern:

*The pattern follows Pascal's triangle.*

Time Complexity: or

Query Complexity:

##### Alternative Solution

Alternatively, observe that if adjacent values are queried, the matrix that is created follows certain patterns. These patterns can be exploited to improve the overall time complexity.

Interestingly, the resulting code is almost identical to that of the official solution.

Time Complexity: or

Query Complexity:

## Comments

Why don't you mention the solution? https://en.wikipedia.org/wiki/Lagrange_polynomial

The solution didn't seem interesting so I didn't include it originally, seeing as it was just copy paste some code/implement an equation. However, it was a pretty big oversight when I first wrote the problem.

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

I challenge you to implement that solution :)

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

Precalculating Pascal's triangle only require time.

Noted, thanks!