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

Многочленами или полиномами (англ. 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$ ошибками.