### PROBLEM LINK:

**Author:** Akul Sareen

**Tester:** Akashdeep Nain

**Editorialist:** Akul Sareen

### DIFFICULTY:

HARD

### PREREQUISITES:

### PROBLEM:

Given the value of l(x) for x = 0,1,…,n-1, find the value of p(x) for x = 0,1,…,n-1 where

**p(x) = a**and

_{1}* x^{1}+ a_{2}* x^{2}+ .... + a_{N}* x^{N}mod(10^{9}+7)**l(x) = a**

_{1}* 1^{x}+ a_{2}* 2^{x}+ .... + a_{N}* N^{x}mod(10^{9}+7)### QUICK EXPLANATION:

The question can be re-written to find the inverse of a matrix. The inverse of this matrix is a Vandermonde matrix, whose inverse can be found using polynomial interpolation techniques.

### EXPLANATION:

Using the definition of l(x) we can re-write the values l(x) we know in the following form:

# $\begin{pmatrix}

1^0 && 2^0 && \ldots && N^0\

1^1 && 2^1 && \ldots && N^1\

\vdots && \vdots && \vdots && \vdots\

1^N && 2^N && \ldots && N^N

\end{pmatrix}

\times

\begin{pmatrix}

a_1\

a_2\

\vdots\

a_N

\end{pmatrix}

\begin{pmatrix}

l(1)\

l(2)\

\vdots\

l(N)

\end{pmatrix}$

which we can write in short as, A \times X = B. Therefore, X = A^{-1} \times B. Once we know X, then we can easily find the value of p(x) at x = 0,1,…,n-1.

So the question boils down to finding A^{-1}. Using Gaussian elimination we can find A^{-1} in \mathcal{O}(N^3). However, this is not fast enough for us.

So, let us look at A once again. It should look strangely familiar to anyone who has performed polynomial interpolation. In fact, if we look at the transpose of A:

A^T = \begin{pmatrix} 1^0 && 1^1 && \ldots && 1^N\\ 2^0 && 2^1 && \ldots && 2^N\\ \vdots && \vdots && \vdots && \vdots\\ N^0 && N^1 && \ldots && N^N \end{pmatrix}

This is a Vandermonde matrix. It is the exact matrix whose inverse we would want to find if we wanted to interpolate a polynomial f(x), given its value at x = 1,2,…,N.

We know polynomials can be interpolated in \mathcal{O}(N^2) time. So hopefully, we will be able to find (A^T)^{-1} in \mathcal{O}(N^2), and then use the fact that (A^T)^{-1} = (A^{-1})^T to find A^{-1}.

Let us consider one of the standard ways of polynomial interpolation using Lagrange polynomials.

This says, that if f(x) = c_1 + c_2x + \dots + c_Nx^{N-1}, and you are only given (x_1,f(x_1)),(x_2,f(x_2)),\dots,(x_N,f(x_N)) then you can recover f(x) as

where

# i.e. $\begin{pmatrix}l_1(x) \ l_2(x) \ \ldots \ l_N(x)\end{pmatrix}

\times

\begin{pmatrix}f(x_1) \ f(x_2) \ \ldots \ f(x_N)\end{pmatrix}^T

\begin{pmatrix}f(x)\end{pmatrix}

$

In fact, if we denote the coefficient of x^j in l_i(x) as l_{i,j}, then we can expand the previous expression to:

# $

\begin{pmatrix}

l_{1,0} && l_{2,0} && \ldots && l_{N,0}\

l_{1,1} && l_{2,1} && \ldots && l_{N,1}\

\vdots && \vdots && \vdots && \vdots\

l_{1,N-1} && l_{2,N-1} && \ldots && l_{N,N-1}

\end{pmatrix}

\times

\begin{pmatrix}

f(x_1)\

f(x_2)\

\vdots\

f(x_N)

\end{pmatrix}

\begin{pmatrix}

c_1\

c_2\

\vdots\

c_N

\end{pmatrix}

$

where c_1,c_2,\dots,c_N are the coefficients of f(x)

Now, if we let x_1 = 1, x_2 = 2, \dots, x_N = N, then we can show:

# $A^T \times

\begin{pmatrix}

c_1\

c_2\

\vdots\

c_N

\end{pmatrix}

\begin{pmatrix}

f(x_1)\

f(x_2)\

\vdots\

f(x_N)

\end{pmatrix}

$

Therefore,

(A^T)^{-1} = \begin{pmatrix} l_{1,0} && l_{2,0} && \ldots && l_{N,0}\\ l_{1,1} && l_{2,1} && \ldots && l_{N,1}\\ \vdots && \vdots && \vdots && \vdots\\ l_{1,N-1} && l_{2,N-1} && \ldots && l_{N,N-1} \end{pmatrix}

This means, we can find A^{-1} quickly if we can find all l_i(x) quickly. To compute all l_i(x) quickly we can first precompute T(x) = \prod_{1 \le i \le N}x - x_i in \mathcal{O}(N^2).

Now,

This calculation can be done in \mathcal{O}(N) for each l_i(x). Hence, we can find all l_i(x) in \mathcal{O}(N^2) time. Using these we can find A^{-1}. After that we can easily find the coefficients of the lopymonial. Once, we have those we can easily evaluate our polynomial at all the required points.

### ALTERNATIVE SOLUTION:

The tester came up with an entirely different approach (I think) which I have no clue about. However, I am attaching it so that if anyone wishes they can consult it.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.