P4512 [Template] Polynomial Division

Given an $n$-degree polynomial $F(x)$ and an $m$-degree polynomial $G(x)$, find polynomials $Q(x)$ and $R(x)$ such that: - $\deg Q(x) = n - m$, and $\deg R(x) < m$. - $F(x) = Q(x) * G(x) + R(x)$. All operations are performed modulo $998244353$.

The first line contains two integers $n$ and $m$, as described above. The second line contains $n+1$ integers, giving the coefficients of $F(x)$ from low to high degree. The third line contains $m+1$ integers, giving the coefficients of $G(x)$ from low to high degree.

The first line contains $n - m + 1$ integers, giving the coefficients of $Q(x)$ from low to high degree. The second line contains $m$ integers, giving the coefficients of $R(x)$ from low to high degree. If $\deg R(x) < m - 1$, pad the remaining coefficients with $0$.

For all testdata, $1 \le m < n \le 10^5$, and the given coefficients belong to $[0, 998244353) \cap \mathbb{Z}$. Translated by ChatGPT 5