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) = 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
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.