Contest Duration: - (local time) (100 minutes) Back to Home
Official

## D - Polynomial division Editorial by en_translator

The Problem Statement asks to find $$\frac{C(x)}{A(x)}$$. The coefficients of $$B(x)$$ can be determined in the decreasing order of its degree in manner of divisions of polynomials.

Formally, the problem can be solved as follows. We generally denote the $$k$$-th coefficient of $$B(x)$$ as $$B_k$$. For $$k > M$$, $$B_k = 0$$. Since $$A(x)$$ is a polynomial of degree $$N$$, by comparing the coefficients of both hand sides of $$C(x)=A(x)B(x)$$, we have the following relation:

• $$C_{N+M}=A_NB_M+A_{N-1}B_{M+1}+\cdots +A_1B_{N+M-1}+A_0B_{N+M}$$
• $$C_{N+M-1}=A_NB_{M-1}+A_{N-1}B_{M}+\cdots +A_1B_{N+M-2}+A_0B_{N+M-1}$$
$$\vdots$$
• $$C_{N+1}=A_NB_1+A_{N-1}B_2+\cdots +A_1B_N+A_0B_{N+1}$$
• $$C_{N}=A_NB_0+A_{N-1}B_1+\cdots +A_1B_{N-1}+A_0B_N$$

Therefore, for $$i=0,1,\ldots, M$$, when we have determined the values of $$B_k$$ for $$k> M-i$$, we can find the value of $$B_{M-i}$$ as

$B_{M-i}=\frac{C_{N+M-i}-A_{N-1}B_{M-i+1}-A_{N-2}B_{M-i+2}\cdots -A_0B_{N+M-i}}{A_N}.$

For $$i=0$$, we have $$B_k=0$$ for $$k> M$$; for $$i=i_0$$ $$(i_0>0)$$, the value of $$B_{M-{i_0}}$$ can be inductively found based on the results for $$i<i_0$$.

The time complexity of this solution is $$O(NM)$$, which is fast enough. Moreover, it can be managed in $$32$$-bit integer type variables without overflows. Therefore, the problem has been solved.

#include <bits/stdc++.h>
using namespace std;

int main(void) {
int n, m;
cin >> n >> m;
vector<int>a(n + 1), b(m + 1), c(n + m + 1);
for (int i = 0; i <= n; i++)cin >> a[i];
for (int i = 0; i <= n + m; i++)cin >> c[i];
for (int i = m; i >= 0; i--) {
b[i] = c[i + n] / a[n];
for (int j = 0; j <= n; j++)c[i + j] -= b[i] * a[j];
}
for (int i = 0; i < m; i++)cout << b[i] << " ";
cout << b[m] << endl;
return 0;
}


posted:
last update: