Fast Fourier Transform을 이용한 빠른 다항식 곱셈 공부하기

1. 두 다항식의 곱셈 다항식 $f(x) = a_{0}x^{0} + a_{1}x^{1} + ... + a_{n-1}x^{n-1}$과 $g(x) = b_{0}x^{0} + b_{1}x^{1} + ... + b_{n-1}x^{n-1}$의 곱셈은.. $f(x)g(x) = a_{0}b_{0}x^{0} + (b_{0}a_{1} + a_{1}b_{0})x^{1} + ... + a_{n-1}b_{n-1}x^{2n-2}$로 나타날 것이다. 다항식을 각각 계수만을 가진 길이가 n인 벡터 A = [a0,a1,...,an-1], B = [b0, b1, ... , bn-1]로 나타낸다고 할때, 두 다항식의 곱셈은 길이가 2n-1인 벡터 C = [c0,c1,...,c(2n-2)]로 나타나며, $$c_{i} = \sum_{j=0..