число сочетаний, алгоритм

[mihatel]

Всем привет! Такой вопрос: по какому алгоритму можно быстро посчитать число сочетаний $\binom{n}{k}$ по некоторому не очень большому модулю? Значение $n$ предполагается около миллиона, $k$ - примерно вдвое меньше. На треугольник Паскаля не хватает памяти, рекуррентные вычисления получаются слишком медленными.

[Pphantom]

Тема перемещена из форума «Программирование» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Программирование»

[arseniiv]

Что можно сделать для простого модуля, разобрали здесь:
https://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n

Непростой модуль хуже, потому что даёт больше необратимых элементов в знаменателе, но кое-как и в таком случае скорее всего можно выкрутиться.

[Andrey A]

mihatel в сообщении #1421375 писал(а):

... быстро посчитать число сочетаний $\binom{n}{k}$ по некоторому не очень большому модулю? Значение $n$ предполагается около миллиона

$\binom{n}{k} \mod m$
Степень вхождения простого модуля в факториал определить легко (см. Википедию). Если $m$ простое, первое что приходит в голову – определить степень вхождения $m$ в $n!,k!,n-k!$ и вычесть из первого второе и третье, получив с большой вероятностью нечто $>0$ (если $m$ действительно не очень большое). Тогда вопрос закрыт. Если же $\binom{n}{k}$ не делится на $m$, приходится то же проделать с остальными простыми делителями факториалов, то есть факторизовать $\binom{n}{k}$. Алгоритм возведения в степень по заданному модулю (уже не обязательно простому) можно посмотреть например у Ишмуратова (Методы факторизации натуральных чисел, стр. 13). Вычислить степени и перемножить по модулю. А как быстрее? Я по ссылке arseniiv не ходил, там всё по-английски), но возможно то и имеется в виду.

[mihatel]

arseniiv в сообщении #1421639 писал(а):

Что можно сделать для простого модуля, разобрали здесь:
https://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n

Непростой модуль хуже, потому что даёт больше необратимых элементов в знаменателе, но кое-как и в таком случае скорее всего можно выкрутиться.

Спасибо! Теорема Ферма - это то, что надо. Суть в том, что делить ничего не надо, достаточно один раз найти обратные элементы по простому модулю и перемножать числитель с остатками знаменателя.