Говорят, что степень многочлена равна $n$, если его наибольший ненулевой коэффициент стоит у $x^n$.
Многочлены, подобно скалярам, можно складывать, вычитать и умножать, получая другие многочлены. Многочлены также можно делить, но результат не всегда получается многочленом. В этом смысле множество многочленов является кольцом, подобно кольцу остатков по модулю.
#Представление многочленов и чисел
Программно представлять многочлен проще всего через vector или обычный статический массив, содержащий его коэффициенты по порядку. Помимо непосредственно многочленов, удобно представлять в таком виде и длинные числа, притворившись, что $x$ равно $10$ или основанию любой другой системы счисления:
При операциях с длинными числами (например, при умножении), можно проводить соответствующую операцию с многочленами, а затем производить каррирование результата: проходить от нижних разрядов получившегося многочлена к верхним и «сдвигать» переполнившиеся разряды:
const int base = 10;
vector<int> normalize(vector<int> a) {
int carry = 0;
for (int &x : a) {
x += carry;
carry = x / base;
x %= base;
}
while (carry > 0) {
a.push_back(carry % base);
carry /= base;
}
return a;
}
vector<int> multiply(vector<int> a, vector<int> b) {
return normalize(poly_multiply(a, b));
}
Из соображений производительности следует выбирать настолько большое основание, насколько вмещается в используемый тип данных (например, $10^9$ или $2^{30}$ для int).
#Коэффициенты разложений
Коэффициенты при $a^x b^y$, получаемые при возведении бинома $(a+b)$ в $n$-ную степень, называются биномиальными коэффициентами:
$$ (a + b)^n = \sum_{k=0}^n C_n^k \cdot a^k \cdot b^{n-k} $$ Их удобно считать по следующей формуле: $$ C_n^k = \binom{n}{k} = \frac{n!}{(n - k)! k!} $$ В более общем случае определяют полиномиальный коэффициент, равный количеству раз, которое элемент $a_1^{x_1} a_2^{x_2} \ldots a_k^{x_k}$ появится при раскрытии скобки $(a_1+a_2+\ldots+a_k)^n$: $$ P(x_1, x_2, \ldots, x_k) = \frac{n!}{\prod (x_i!)} $$Биномиальные коэффициенты применяются в комбинаторике и в отрыве от многочленов. В задачах по программированию их подсчет часто требуется проводить по модулю, для чего нужно уметь искать обратные к факториалам.
#Умножение многочленов
При умножении двух многочленов степени $n$ и $m$ получается многочлен степени $(n+m)$. Прямая формула для произведения многочленов имеет вид
$$ \left(\sum_{i=0}^n a_i x^i\right)\cdot\left(\sum_{j=0}^m b_j x^j\right)=\sum_{k=0}^{n+m}x^k\sum_{i+j=k}a_i b_j $$Её наивный подсчёт требует $O(n^2)$ операций, но далее в этой главе мы разберем несколько более эффективных алгоритмов — самый быстрый из которых работает всего за $O(n \log n)$.
Этот факт позволяет сводить много комбинаторных задач к произведению многочленов и использованию уже известных алгоритмов для его подсчета. Разберем несколько примеров таких задач.
#2-рюкзак
Даны два массива $a$ и $b$ размера $n$ и $m$. Требуется найти число различных возможных сумм $(a_i + b_j)$.
$n, m, a_i, b_i \le 10^5$.
Рассмотрим многочлены $A(x)$ и $B(x)$, в которых коэффициент при $k$-той степени равен числу равных $k$ элементов в соответствующем массиве.
Рассмотрим произведение $C = A \cdot B$. В получившемся многочлене коэффициент $c_t$ при $x^t$ будет равен
$$ c_t \cdot x^t = \sum_{p+q=t} a_p \cdot b_q \cdot x^{p+q} $$что в свою очередь равно количеству способов набрать сумму ровно $t$.
Значит, мы можем перемножить эти два многочлена за $O(n \log n)$ и просто подсчитать число ненулевых коэффициентов результата.
#Мульти-рюкзак
Задача «Вор в магазине» является небольшой модификацией предыдущей:
Имеется $n$ типов предметов различных целых стоимостей $a_i$. Требуется найти количество различный сумм стоимостей наборов из ровно $k$ предметов (возможно, с повторениями).
$n, k, a_i \le 1000$
Опять же, рассмотрим многочлен, в котором коэффициент при $i$-той степени равен единице, если существует предмет со стоимостью $i$, и нулю в противном случае.
Если $k=2$, наша задача свелась к предыдущей: нужно домножить многочлен на самого себя и посмотреть на число ненулевых коэффициентов. В общем же случае нам нужно возвести многочлен в степень $k$ и также посчитать ненулевые коэффициенты результата.
Если возводить многочлен в $k$-ную степень наивно, то асимптотика такого решения будет $O(n k^2 \log (nk))$: нужно $O(k)$ раз перемножать два многочлена, больший из которых имеет длину $O(nk)$.
Воспользуемся бинарным возведением в степень: умножение многочленов ведь ассоциативно. В данном случае асимптотика будет не более $O(nk \log (nk) \log k)$: нужно $O(\log k)$ раз умножать два многочлена порядка $O(nk)$. Но на самом деле, так как на каждой итерации размер многочлена будет увеличиваться в два раза, в асимптотике учтется только последнее (самое большое) умножение, и поэтому в действительности время работы составит $O(nk \log (nk))$.
#Свёртки
Свёрткой (англ. convolution) называется операция применения некоторой «оконной» функции ко всем отрезкам фиксированной длины исходной функции.
В дискретном случае свертке соответствует сумме вида
$$ (f * g)(x)= f(1) \cdot g(x-1) + f(2) \cdot g(x-2) + \dots + f(k) \cdot g(x - k) $$ В ещё более узком смысле, свертка это результат перемножения многочленов: $$ (A \cdot B)_k = a_0 \cdot b_k + a_1 \cdot b_{k-1} + \ldots + a_k \cdot b_0 $$то есть $k$-тый коэффициент результата равен применению какой-то оконной функции, заданной коэффициентами $B(x)$, к коэффициентам $A(x)$. Значит, подобные функции можно быстро считать через матричное умножение.
Например, так можно (неэффективно) искать битовую подстроку $t$ в строке $s$: запишем символы $s$ как коэффициенты многочлена $A(x)$ и символы $t$ в обратном порядке как коэффициенты многочлена $B(x)$ и перемножим. В позициях многочлена-результата, где коэффициенты равны $|t|$, строка $t$ входит в $s$.
Также с помощью этого трюка можно решать и другие задачи, например выполнять «fuzzy searching»: коэффициенты, равные $(|t|-d)$, соответствуют вхождениям с ровно $d$ ошибками.