P3803 【Template】Polynomial Multiplication (FFT)

This is a template problem for polynomial multiplication. Note: This problem is not within the CCF-defined Senior knowledge points.

Given a degree $n$ polynomial $F(x)$ and a degree $m$ polynomial $G(x)$, compute the product $F(x)$ and $G(x)$.

The first line contains two integers $n, m$. The next line contains $n+1$ integers, representing the coefficients of $F(x)$ from lowest degree to highest. The next line contains $m+1$ integers, representing the coefficients of $G(x)$ from lowest degree to highest.

Output one line containing $n+m+1$ integers, representing the coefficients of $F(x) \cdot G(x)$ from lowest degree to highest.

It is guaranteed that all input coefficients are integers between $0$ and $9$ inclusive. For $100\%$ of the testdata: $1 \le n, m \leq {10}^6$. Translated by ChatGPT 5