I have recently learned FFT and how we can multiply polynomials in n * logn. I sometimes struggle in coming up with the polynomials and how they should be multiplied in the context of the problem. For example in this problem. https://open.kattis.com/problems/kinversions we have to calculate the inversions.
We have to multiply polynomials but how to come up with the polynomial and whether the second polynomial should be inverted/rotated/shifted before being multiplied?
Like something these for the polynomials multiplied
0 1 0 1 _ _ _ _
_ _ _ _ 0 1 0 1
or
0 1 0 1 _ _ _ _
_ _ _ _ 1 0 1 0
or
0 1 0 1 _ _ _ _
1 0 1 0 _ _ _ _
where 0 is B and 1 is A.
Thanks!!