title: "CF 1531E3 - \u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c" description: "Let $U(x)$ and $V(x)$ be polynomials of degree $r$ with integer coefficients, and let $W(x) = U(x)V(x)$ so that $W(x)$ has degree $2r$. Write $$U(x) = sum{i=0}^{r} Ui x^i, qquad V(x) = sum{i=0}^{r} Vi x^i, qquad W(x) = sum{k=0}^{2r} Wk x^k." date: "2026-06-10T16:49:40+07:00" tags: ["codeforces", "competitive-programming", "*special", "binary-search"] categories: ["algorithms"] codeforces_contest: 1531 codeforces_index: "E3" codeforces_contest_name: "VK Cup 2021 - \u041a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f (Engine)" rating: 0 weight: 1531 solve_time_s: 98 verified: false draft: false --- CF 1531E3 - \u0421\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u0435\u043c Rating: - Tags: *special, binary search Solve time: 1m 38s Verified: no ## Solution ## Solution Let $U(x)$ and $V(x)$ be polynomials of degree $r$ with integer coefficients, and let $W(x) = U(x)V(x)$ so that $W(x)$ has degree $2r$. Write$$U(x) = \sum_{i=0}^{r} U_i x^i, \qquad V(x) = \sum_{i=0}^{r} V_i x^i, \qquad W(x) = \sum_{k=0}^{2r} W_k x^k.$$ The goal is to determine the coefficients $W_k$ from structured evaluations of $U(x)$ and $V(x)$. Define evaluation points $$x_0, x_1, \ldots, x_{2r}$$ as $2r+1$ distinct integers. For each $j$ define $$P_j = U(x_j), \qquad Q_j = V(x_j), \qquad R_j = W(x_j) = P_j Q_j.$$ The key identity is that the coefficient vector $(W_0,\ldots,W_{2r})$ is uniquely determined by the values $(W(x_0),\ldots,W(x_{2r}))$ because interpolation in a degree-$2r$ space is uniquely solvable. Let $A$ be the $(2r+1)\times(2r+1)$ matrix with entries $$A_{j,k} = x_j^k.$$ Then the evaluation relation is $$R = A W,$$ where $R = (W(x_0),\ldots,W(x_{2r}))^T$ and $W = (W_0,\ldots,W_{2r})^T$. Since the $x_j$ are distinct, $A$ is a Vandermonde matrix and therefore invertible. Hence $$W = A^{-1} R.$$ This expresses each coefficient $W_k$ as a fixed linear combination of the values $W(x_j)$: $$W_k = \sum_{j=0}^{2r} \lambda_{k,j} W(x_j),$$ where $\lambda_{k,j}$ are constants depending only on the chosen points $x_j$. Each value $W(x_j)$ is computed as a single multiplication of numbers of size at most $n + O(1)$ bits: $$W(x_j) = U(x_j)V(x_j),$$ and the evaluation of $U(x_j)$ and $V(x_j)$ uses only additions and multiplications by fixed constants, hence requires $O(n)$ elementary operations when $r$ is fixed. The final reconstruction step computes each $W_k$ as a sum of $2r+1$ precomputed values multiplied by fixed constants $\lambda_{k,j}$. This is a constant-size linear transformation applied to numbers of size $O(n)$ bits, so it also requires $O(n)$ operations. Thus the computation of all coefficients $W_k$ requires exactly $2r+1$ multiplications of $n$-bit numbers plus linear-time combination steps. The identity (25) follows directly from the structure of the interpolation process: the coefficients of $W(x)$ are obtained by applying the inverse Vandermonde transformation to the vector of values $(W(0),\ldots,W(2r))$, and this transformation is linear with fixed coefficients independent of $u$ and $v$. This completes the proof. ∎