nCr с предварительно вычисленными факториалами

Во многих задачах требуется определить, сколькими способами можно выбрать r элементов из n; это записывается как nCr. В задачах на соревнованиях этот подсчёт выполняется по простому модулю. 🧮

Классическая формула гласит: nCr равно n факториал, делённый на произведение факториала r и факториала n минус r. Подвох в том, что деление по модулю.

Один факториал растёт астрономически быстро, поэтому каждый из них вычисляют по модулю p. Так каждое значение остаётся небольшим, а формула сохраняет точность по этому модулю.

Один раз создайте массив fact до наибольшего нужного значения n. Каждый элемент получают умножением предыдущего элемента на индекс с последующим взятием остатка по модулю p.

Формула делит на два факториала, поэтому Вам нужны их обратные элементы по модулю. Вспомните: обратный элемент превращает деление в обычное умножение.

Вычислите обратный элемент наибольшего факториала всего один раз по теореме Ферма, используя pow с показателем p минус 2. Этот единственный вызов послужит началом для остальных вычислений.

Получите остальные обратные факториалы одним проходом с конца: каждый вычисляется через следующий элемент, умноженный на индекс. Дополнительные вызовы pow не нужны.

Теперь nCr — это просто fact[n], умноженный на inv_fact[r] и на inv_fact[n минус r], с взятием остатка по модулю p. Для каждого запроса нужны три обращения к массиву и два умножения.

После предварительных вычислений ответ для каждого сочетания находится за O(1). Поэтому этот подход особенно хорош, когда задача запрашивает тысячи значений nCr.

Если r отрицательно или больше n, ответ равен 0. Сначала проверьте это ограничение, чтобы не выйти за пределы массивов факториалов.

Задайте размер массива равным максимальному n среди всех запросов плюс небольшой запас. Слишком маленькое ограничение часто приводит здесь к ошибкам индексации.

Насколько быстро выполняется один запрос nCr после предварительных вычислений?

Теперь Вы один раз вычисляете факториалы и обратные элементы для них, а затем отвечаете на каждый запрос nCr за O(1) с помощью трёх обращений к массивам. Проверяйте границы r и задавайте массивы достаточно большого размера. 🏆