Где применяется
1. Задача
Шаг 136 быстро возводил число в большую степень, а шаг 137 держал числа маленькими с помощью модуля. Теперь ответ сам по себе это количество: дано n предметов, сколькими разными способами можно выбрать из них r, если порядок не важен?
Это количество записывают как C(n, r) и читают «из n по r» (число сочетаний). Выбрать 2 друзей из 5: C(5, 2) = 10. Сдать 5 карт из колоды в 52: C(52, 5) = 2 598 960. Формула из учебника: n! / (r! · (n - r)!), где n! (читается «эн факториал») это произведение 1 · 2 · 3 · ... · n.
В этой формуле есть ловушка. n! растёт очень быстро: 13! уже больше 6 миллиардов, 21! не помещается даже в 64-битное целое. У 52! уже 68 цифр. Если посчитать три факториала по отдельности, переполнение наступит задолго до того, как деление вернёт ответ к небольшому числу вроде 2 598 960.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на подсчёт, где нужно число сочетаний из n по r, например пути в сетке, отсортированные строки или порядки, которые сохраняют форму. Треугольник Паскаля складывает два числа на клетку, огромный факториал не появляется, и всё работает по модулю 10^9 + 7.
Построй треугольник строка за строкой. Это сама таблица урока.
Нужна только одна строка, так что обновляй один массив справа налево.
Отсортированная строка длины n из 5 гласных это выбор с повторами, C(n + 4, 4), который берётся прямо из треугольника.
Если d это расстояние, нужно (k + d) / 2 шагов вправо из k, так что ответ это C(k, (k + d) / 2) по модулю 10^9 + 7, или 0, если d больше k или не совпадает чётность.
Левое и правое поддеревья можно перемешать C(left + right, left) способами, так что умножай это на ответы обоих поддеревьев и в конце вычти 1.