Многочлены, Горнер и генерирующие функции

Многочлены и схема Горнера для быстрого вычисления, плюс обзорный взгляд на генерирующие функции.

Схема Горнера вычисляет значение многочлена в точке за n умножений и n сложений, переписывая его во вложенную форму.

Зачем это в олимпиадах

Многочлены прячутся во многих задачах: полиномиальное хеширование строк, интерполяция, производящие функции для подсчёта. Базовый навык — быстро и устойчиво вычислять значение многочлена; наивная формула со степенями x^k делает лишнюю работу и в целых числах раздувает промежуточные значения. Схема Горнера решает это элегантно и лежит в основе хешей. А генерирующие функции — мощный, хоть и более продвинутый, метод подсчёта: он превращает комбинаторные задачи в операции с рядами. Дадим работающий минимум по обоим.

Схема Горнера

Многочлен P(x) = c₀xⁿ + c₁xⁿ⁻¹ + … + cₙ наивно требует считать каждую степень x^k отдельно — лишние умножения. Горнер переписывает его вложенно: P(x) = (…((c₀·x + c₁)·x + c₂)·x + …)·x + cₙ. Теперь достаточно идти по коэффициентам слева направо, на каждом шаге умножая накопленное на x и прибавляя следующий коэффициент. Всего n умножений — вдвое меньше, чем наивно.

def horner(coeffs, x):
    result = 0
    for c in coeffs:        # коэффициенты от старшего к младшему
        result = result * x + c
    return result

# P(x) = 2x^3 - 6x^2 + 2x - 1, вычислим в x = 3
coeffs = [2, -6, 2, -1]
print(horner(coeffs, 3))        # 2*27 - 6*9 + 2*3 - 1 = 5
# проверка прямой формулой
x = 3
print(2*x**3 - 6*x**2 + 2*x - 1)

Вывод:

5
5

Горнер дал 5 — совпало с прямым вычислением. Преимущество не только в скорости: вложенная форма минимизирует промежуточные величины, что важно для хеширования по модулю, где каждый шаг result = (result·x + c) % mod держит число маленьким.

Полиномиальное хеширование — применение Горнера

Хеш строки — это значение многочлена, где коэффициенты — коды символов, а x — фиксированное основание p, всё по модулю M. Схема Горнера вычисляет его за один проход по строке. Это основа быстрого сравнения подстрок (детали алгоритма — в курсе по алгоритмам; здесь нам важна математика).

def poly_hash(s, base=131, mod=10**9 + 7):
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % mod    # ровно схема Горнера по модулю
    return h

print(poly_hash("abc"))
print(poly_hash("abd"))     # другой хеш — строки различны
print(poly_hash("abc") == poly_hash("abc"))   # одинаковые строки — равный хеш

Вывод:

1677554
1677555
True

Генерирующие функции: идея

Генерирующая (производящая) функция последовательности a₀, a₁, a₂, … — это формальный степенной ряд A(x) = a₀ + a₁x + a₂x² + …, где коэффициент при x^k кодирует k-й член.

Идея гениальна: «повесить» всю последовательность на коэффициенты ряда и работать с рядом как с единым объектом. Главное чудо — произведение генерирующих функций соответствует свёртке последовательностей: коэффициент при x^k в A(x)·B(x) равен ∑_i aᵢ·b_k−i. Это ровно «сколькими способами получить сумму k, взяв что-то из A и что-то из B» — а значит, умножение рядов решает комбинаторные задачи на подсчёт.

Классический пример: сколькими способами получить сумму k при броске двух кубиков? Грань кубика кодируется рядом x+x²+…+x⁶ (по коэффициенту 1 на каждую грань). Произведение двух таких рядов даёт распределение сумм: коэффициент при x^k — число способов выбросить сумму k.

def poly_mul(A, B):
    res = [0] * (len(A) + len(B) - 1)
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            res[i + j] += a * b          # свёртка: вклад в степень i+j
    return res

# Кубик: коэффициенты x^1..x^6 (индекс = значение грани)
die = [0, 1, 1, 1, 1, 1, 1]              # die[k] = способов выбросить k одним кубиком
two = poly_mul(die, die)                  # распределение суммы двух кубиков
for s in range(2, 13):
    print(s, two[s])                      # число способов получить сумму s

Вывод:

Коэффициенты 1,2,3,4,5,6,5,4,3,2,1 — в точности число способов выбросить каждую сумму (всего ∑ = 36, как и исходов). Произведение многочленов посчитало всю свёртку разом. Так генерирующие функции сводят «сколько способов набрать сумму» к перемножению рядов — мощный приём для задач о разбиениях, размене монет, подсчёте комбинаций.

Где это работает дальше

Генерирующие функции — большая тема. Они дают замкнутые формулы для рекуррент (Фибоначчи через x/(1−x−x²)), решают задачи о размене и разбиениях, а в связке с быстрым преобразованием Фурье (БПФ/FFT) перемножают многочлены за O(n·log n) — это уже продвинутый алгоритмический инструмент. Для старта достаточно усвоить: ряд кодирует последовательность, а умножение рядов — это свёртка.

Разбор задачи: размен монет через произведение рядов

Генерирующие функции блестяще решают задачу о размене: сколькими способами набрать сумму S монетами заданных номиналов (каждого номинала сколько угодно)? Монета номинала c кодируется рядом 1 + x^c + x^2c + … (взять 0, 1, 2, … таких монет). Произведение рядов по всем номиналам даёт ряд, где коэффициент при x^S — искомое число способов. На практике это превращается в простую динамику — «бесконечный» ряд каждой монеты обрабатывается одним проходом.

def count_change(coins, target):
    # dp[s] = число способов набрать сумму s
    dp = [1] + [0] * target           # один способ набрать 0 — пустой набор
    for c in coins:
        for s in range(c, target + 1):
            dp[s] += dp[s - c]        # добавляем монету номинала c
    return dp

ways = count_change([1, 2, 5], 5)
print(ways)                           # способы набрать 0,1,2,3,4,5
print("Способов набрать 5:", ways[5])

Вывод:

[1, 1, 2, 2, 3, 4]
Способов набрать 5: 4

Сумму 5 монетами {1,2,5} можно набрать 4 способами: 5, 2+2+1, 2+1+1+1, 1×5. Массив dp — это в точности коэффициенты произведения трёх рядов (по одному на номинал), посчитанные эффективно: вложенный цикл по монете «домножает» текущий ряд на 1/(1−x^c). Так абстрактная идея «умножение рядов = свёртка» становится коротким и быстрым кодом — это и есть практическая сила генерирующих функций.

Подводные камни

Порядок коэффициентов в Горнере. Идём от старшего к младшему; перепутаете — получите другой многочлен.
Хеш-коллизии. Полиномиальный хеш может совпасть у разных строк; для надёжности берут два модуля. Хеш — не доказательство равенства.
Свёртка наивно — O(n²). Для больших многочленов нужен FFT; poly_mul выше учебный.
Генерирующие функции — формальные ряды. Сходимость не важна, важны коэффициенты; не путайте с обычными функциями.

Итог

Схема Горнера: result = result·x + c по коэффициентам — n умножений, основа хешей.
Полиномиальный хеш строки — Горнер по модулю.
Генерирующая функция кодирует последовательность коэффициентами ряда.
Произведение рядов = свёртка: умножение многочленов считает «число способов набрать сумму».