Всем привет!
В спортивном программировании линейные рекурренты с постоянными коэффициентами — это стандартная тема. Такие задачи обычно решаются построением матрицы переходов и использованием бинарного возведения в степень для нахождения $$$N$$$-го члена за время $$$O(\log N)$$$ (или с помощью алгоритма Бостана-Мори для больших порядков).
Однако подход должен измениться, если коэффициенты не постоянны, а зависят от $$$n$$$.
Что такое голономная последовательность?
Последовательность $$$a_n$$$ называется голономной (или P-рекурсивной), если она удовлетворяет линейному рекуррентному соотношению, коэффициентами в котором выступают многочлены от $$$n$$$.
Формально это значит, что существуют такие многочлены $$$P_0(x), P_1(x), \dots, P_k(x)$$$ (причем $$$P_k \neq 0$$$), что для любого $$$n$$$ выполняется:
Целое число $$$k$$$ — это порядок рекурренты, а максимальная степень среди многочленов $$$P_i$$$ — степень рекурренты.
Классические примеры:
- Факториалы: $$$1 \cdot a_n - n \cdot a_{n-1} = 0$$$. (Порядок 1, Степень 1).
- Числа Каталана: $$$(n+2) \cdot C_{n+1} - (4n+2) \cdot C_n = 0$$$. (Порядок 1, Степень 1).
- Число беспорядков (Derangements): $$$1 \cdot D_n - (n-1) \cdot D_{n-1} - (n-1) \cdot D_{n-2} = 0$$$. (Порядок 2, Степень 1).
Применение в спортивном программировании
Ключевое свойство голономных последовательностей заключается в их замкнутости относительно различных операций. Если последовательности $$$A$$$ и $$$B$$$ голономны, то следующие последовательности также голономны:
- $$$A + B$$$
- $$$A \cdot B$$$
- Частичные суммы: $$$\sum_{i=0}^n A_i$$$
Это означает, что для сложных сумм, таких как $$$\sum_{k=0}^n \binom{n}{k}^2 \binom{n+k}{k}^2$$$ (числа Апери), математически гарантируется существование полиномиальной рекурренты, поскольку биномиальные коэффициенты и факториалы сами по себе голономны.
Аналитически эти рекурренты могут быть найдены с использованием алгоритма Цайльбергера (Creative Telescoping), который алгебраически упрощает суммирование.
Однако реализация алгоритма Цайльбергера во время контеста крайне непрактична. Так как теоретически гарантировано, что рекуррента существует, можно обойти аналитический вывод и вместо этого угадать рекурренту алгоритмически.
Автоматическое угадывание с помощью метода Гаусса
Рассмотрим сценарий, когда $$$N$$$-й член последовательности нужно найти за время $$$O(N)$$$ (для $$$N \le 10^7$$$), но доступный метод прямого подсчета или динамического программирования требует $$$O(N^2)$$$. Для автоматического вывода лежащей в основе рекурренты можно использовать линейную алгебру.
Предположим, что рекуррента имеет небольшой порядок $$$R$$$ (например, $$$R=2$$$) и полиномиальную степень $$$D$$$ (например, $$$D=1$$$). Уравнение принимает следующий вид:
Поскольку значения $$$a_n, a_{n-1}, a_{n-2}$$$ и $$$n$$$ известны, единственными неизвестными являются константы $$$c_{i,j}$$$. Существует ровно $$$U = (R+1) \times (D+1)$$$ неизвестных констант. В данном примере $$$U = 3 \times 2 = 6$$$.
Реализация (C++)
Ниже представлено мое решение задачи 506E (Mr. Kitayuta's Gift) с использованием этого алгоритма.
Задача 506E: Дана строка $$$S$$$ ($$$|S| \le 200$$$). Вычислите количество валидных способов вставить ровно $$$N$$$ символов ($$$N \le 10^9$$$) так, чтобы итоговая строка стала палиндромом. Все вычисления должны производиться по модулю $$$10007$$$.
Как работает мое решение:
- Наивное ДП: Мы пишем простое $$$O(|S|^2 \cdot K)$$$ ДП для вычисления ответов на небольших длинах.
- Разделение по четности (Важно): Палиндромы четной и нечетной длины ведут себя как две независимые последовательности. Если их смешать, порядок рекурренты раздувается до $$$\sim 600$$$, что вызывает превышение лимита времени (TLE) при матричном умножении. Вычисляя элементы исключительно для целевой четности $$$(|S| + N) \pmod 2$$$, мы уменьшаем порядок рекурренты вдвое, до $$$\le 305$$$.
- Автоматическое угадывание: Мы генерируем $$$K = 800$$$ элементов и подаем их в алгоритм метода Гаусса с полиномиальной степенью $$$D=0$$$ (что по сути находит рекурренту с постоянными коэффициентами).
- Оптимизированное матричное умножение: Мы строим матрицу переходов и возводим её в степень $$$N/2$$$. Поскольку $$$MOD = 10007$$$, мы можем безопасно опустить операцию взятия по модулю в самом внутреннем цикле матричного умножения, позволяя решению уверенно отрабатывать за $$$\sim 0.3s$$$.
Если есть какие-либо вопросы по этому методу или его реализации, пожалуйста, не стесняйтесь оставлять комментарии или писать в личные сообщения.
