 # SATA05 - Editorial

Practice

Contest

Author: Akul Sareen

Tester: Akashdeep Nain

Editorialist: Akul Sareen

HARD

### PREREQUISITES:

Polynomial interpolation

### 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) = a1 * x1 + a2 * x2 + .... + aN * xN mod(109+7) and l(x) = a1 * 1x + a2 * 2x + .... + aN * Nx mod(109+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

f(x) = \sum_{i = 1}^{N}l_i(x) \times f(x_i)

where

l_i(x) = \prod_{0 \le j \le N, j \ne i} \frac{x - x_j}{x_i - x_j}

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

l_i(x) = \frac{T(x)}{x - x_i}\prod_{0 \le j \le N, j \ne i} \frac{1}{x_i - x_j}

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.