Задача 76247

Тема:    [ Многочлены ]

Сложность: 4 Классы:

Условие

Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n. Придумать более эффективный (для больших n) алгоритм, которому достаточно порядка n^{log 4/log 3} действий.

Подсказка

Представим себе, что надо перемножить два многочлена степени 2k. Их можно представить в виде

A(x)x^k + B(x)    и    C(x)x^k + D(x).

Произведение их равно

A(x)C(x)x^2k + (A(x)D(x) + B(x)C(x))x^k + B(x)D(x).

Естественный способ вычисления AC, AD + BC, BD требует четырёх умножений многочленов степени k, однако их количество можно сократить до трёх с помощью такой хитрости: вычислить AC, BD и  (A + B)(C + D), а затем заметить, что AD + BC = (A + B)(C + D) - AC - BD.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	2
Название	Массивы
задача
Номер	1.2.16