Как мы можем вычислить N, выбрав модуль K простым числом без переполнения?

Question

Как мы можем компьютер ( N выбрать K )% M в C или C ++, не вызывая переполнение?

Для конкретного случая, когда N (4 <= N <= 1000) </strong> и K (1 <= K <= N) </strong> и M = 1000003 .

Answer 1

Чтобы вычислить (n выберите k)% M, вы можете отдельно вычислить модуль M для знаменателя (n!) И модуль M для знаменателя (k! * (N - k)!), А затем умножить знаменатель на модульный модуль знаменателя. мультипликативный обратный (в М). Поскольку M простое число, вы можете использовать маленькую теорему Ферма для вычисления мультипликативного обратного.

Есть хорошее объяснение с примером кода по следующей ссылке (проблема SuperSum):

http://www.topcoder.com/wiki/display/tc/SRM+467

Answer 2

Поскольку 1000000003 = 23 * 307 * 141623, вы можете рассчитать (n выбирает k) mod 23, 307 и 141623, а затем применить теорему китайского напоминания [1].При расчете n !, k!и (nk) !, вы должны рассчитывать каждый мод 23, 307 и 141623 каждый шаг, чтобы предотвратить переполнение.

Таким образом, вы должны избегать переполнения даже на 32-битных машинах.

Небольшое улучшение будетбыть для вычисления (n выбирает k) мод 141623 и 7061 (23 * 307) (редактировать: но это может быть немного сложно вычислить обратный модуль 7061, поэтому я бы не стал это делать)

I 'извините за мой плохой английский.

[1] http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Edit2: Еще одна потенциальная проблема, которую я обнаружил, - это вычисление n!mod 23 (например) это, вероятно, будет 0, но это не означает, что (n выбирает k) равно 0 mod 23, поэтому вы должны посчитать, сколько раз 23 делит n !, (nk)!и к!перед расчетом (n выбирает k).Вычислить это легко, р делит п!ровно пол (н / п) + пол (н / п²) + ... раз.Если так получится, что 23 делит n!в то же время он делит к!и (nk) !, вы продолжаете вычислять (n выбирает k) mod 23, делив его на 23 каждый множитель каждый раз. То же самое относится к 307, но не к 141623

Answer 3

Вы можете использовать рекурсивную формулу по ссылке, которую вы дали, и выполнить мод расчета M.

Answer 4

Вот простой пример:

(A * B * C) % N ... is equal to... ((A % N) *  (B % N) * (C % N)) % N;

То есть все, что вам нужно, чтобы применить модуль к каждому операнду и продукту, или как только он станет большим числом. И последний модуль должен применяться к общему результату.

Answer 5

Используйте приближение Стирлинга для расчета биномиального коэффициента.Затем просто рассчитайте модуль как обычно.