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 1. 0 1 0 1 — — — - - — — — 0 1 0 1
- 0 1 0 1 — — — -
-
-
-
- 1 0 1 0
-
-
where 1 is B and 0 is A.
Thanks!!