FFT for expanded form of equation multiplication

Question

I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?

For example, if you are multiplying $A(x) = 1 + 2x + 6x^2$ and $B(x) = 4 + 5x + 3x^2$ such that you get $C(x) = A(x) \cdot B(x) = 4 + 5x + 3x^2 + 8x + 10x^2 + 6x^3 + 24x^2 + 30x^3 + 18x^4$ without going directly to the simplified answer?

Furthermore, is it possible to use FFT to do this expanded form multiplication in $O(n\,log\,n)$ time? If so, can you show me how to apply FFT to this scenario?

Answer 1

The trivial algorithm that multiplies every monomial in $A$ by every monomial in $B$ takes time $O(|A| \cdot |B|)$ (where $|A|$ is the number of monomials in $A$ or $\deg A + 1$, depending on the representation), which is the same order of magnitude as the size of the output, and so optimal. You only need FFT if you want to actually compute the product $AB$. In particular, there is no way to compute your function in time $O(n\log n)$, simply because the length of the output is $\Omega(n^2)$.