Многочлены - Алгоритмика
Многочлены

Многочлены

автор Сергей Слотин
обновлено сент. 14, 2021
Многочленами или полиномами (англ. polynomial) называются конечные суммы вида $$ P(x_1, x_2, \ldots, x_n) = \sum_{I=\{i_1,i_2,\ldots,i_n\}} c_I \cdot x_1^{i_1} \cdot x_2^{i_2} \cdot \ldots \cdot x_n^{i_n} $$ В частности, многочлены от одной переменной это суммы вида $$ P(x) = c_0 + c_1 x^1 + \ldots + c_n x^n $$

Говорят, что степень многочлена равна $n$, если его наибольший ненулевой коэффициент стоит у $x^n$.

Многочлены, подобно скалярам, можно складывать, вычитать и умножать, получая другие многочлены. Многочлены также можно делить, но результат не всегда получается многочленом. В этом смысле множество многочленов является кольцом, подобно кольцу остатков по модулю.

Представление многочленов и чисел

Программно представлять многочлен проще всего через vector или обычный статический массив, содержащий его коэффициенты по порядку. Помимо непосредственно многочленов, удобно представлять в таком виде и длинные числа, притворившись, что $x$ равно $10$ или основанию любой другой системы счисления:

$$ \begin{aligned} A(x) &= a_0 + a_1\cdot x + a_2 \cdot x^2 + \dots + a_n \cdot x^n \\ &= a_0 + a_1\cdot 10 + a_2 \cdot 10^2 + \dots + a_n \cdot 10^n \end{aligned} $$

При операциях с длинными числами (например, при умножении), можно проводить соответствующую операцию с многочленами, а затем производить каррирование результата: проходить от нижних разрядов получившегося многочлена к верхним и «сдвигать» переполнившиеся разряды:

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$ ошибками.