Задача

Даны два полинома: $$$A = a_{0} + a_{1} \cdot x + \dots + a_{n-1} \cdot x^{n-1}$$$ и $$$B = b_{0} + b_{1} \cdot x + \dots + b_{n-1} \cdot x^{n-1}$$$. Для удобства будем записывать их как $$$[a_{0}, a_{1}, \cdot a_{n-1}]$$$ и $$$[b_{0}, b_{1}, \cdot b_{n-1}]$$$. Необходимо найти полином $$$C = A \cdot B$$$. Его размер равен $$$2n$$$.

Тривиальное решение

Задачу можно решить за асимптотику $$$O(n^{2})$$$, напрямую посчитав $$$C = A \cdot B = [a_{0} \cdot b_{0}, a_{0} \cdot b_{1} + a_{1} \cdot b_{0}, \dots ] = [\sum\limits_{i \in [0,0]}(a_{i} \cdot b_{0-i}), \sum\limits_{i \in [0,1]}(a_{i} \cdot b_{1-i}), \dots, \sum\limits_{i \in [0,k]}(a_{i} \cdot b_{k-i}), \dots]$$$.

План решения

Решение с помощью быстрого преобразования Фурье будет состоять из трех шагов: 1. Вычислить $$$A(x_{0}), A(x_{1}), \dots A(x_{2n-1})$$$ и $$$B(x_{0}), B(x_{1}), \dots B(x_{2n-1})$$$. 2. Вычислить значение $$$C$$$ в точках: $$$C(x_{0}) = A(x_{0}) \cdot B(x_{0}), C(x_{1}) = A(x_{1}) \cdot B(x_{1}), \dots C(x_{2n-1}) = A(x_{2n-1}) \cdot B(x_{2n-1})$$$. 3. Интерполировать $$$C$$$ по известным $$$2n$$$ значениям.

Вычисление значения полинома в точке в общем случае решается за $$$O(n)$$$. Поэтому первый шаг требует

Unable to parse markup [type=CF_MATHJAX]

. Интерполяция полинома решается в общем случае за $$$O(n^{2})$$$ с помощью интерполяционной формулы Лагранжа. Итоговая асимптотика решения для произвольных $$$x_{0}, x_{1}, \dots x_{2n-1}$$$ — O(n^{2}). Количество действий может быть существенно уменьшено, если выбрать $$$x_{0}, x_{1}, \dots x_{2n-1}$$$ особым образом.