nCr mod 10^9 + 7 для n<=10^9 и r <=1000

Это, возможно, задавали раньше, но ни один из ответов, которые я видел, не работал для меня. Я попробовал теорему Лукаса, теорему Ферма, но ни одна из них не сработала. Есть ли эффективный способ найти значение:

nCr mod 10^9+7 where n<=10^9 and r<=1000

Любая помощь будет очень полезна

Источник

1 ответ

Решение

n большое, а r маленькое, лучше вычислить nCr по n(n-1)...(n-r+1)/(1*2*...*r)

Возможно, вам понадобится найти обратное множитель 1, 2, ... r mod 10^9+7

Источник
Другие вопросы по тегам