Как мы можем вычислить компьютер (N choose K)% M на C или C++ без вызова переполнения?Как мы можем вычислить N, выбрать K-модуль, простое число без переполнения?
В частном случае, когда N (4 < = N < = 1000) и К (1 < < = К = Н) и М = 1000003.
Чтобы вычислить (n выбрать k)% M, вы можете отдельно вычислить модуль nominator (n!) M и знаменатель (k! * (N - k)!) Модуля M, а затем умножить номинатор на знаменатель модулярный мультипликативный обратный (в M). Так как M является простым, вы можете использовать Маленькую теорему Ферма для вычисления мультипликативного обратного.
Существует хорошее объяснение с примерами кода, по следующей ссылке (проблема SuperSum):
Для некоторой дополнительной скорости вычислите числитель как произведение из (K + 1) в N , и знаменатель как K !. Мы знаем, что в расчете не будет никаких коэффициентов M, потому что они простые и больше N. Следовательно, мы можем отменить верх и низ, не беспокоясь о том, что то, что мы отменяем, может быть кратным M (т. Е. 0). –
Точно я узнал из того же. – Quixotic
Но теперь я вижу, что 1,000,000,003 не является простым, любая идея, как решить это сейчас? – Quixotic
Вы можете использовать рекурсивную формулу по ссылке вы дали и сделать расчет мод М.
Использование Stirling's approximation для вычисления биномиального коэффициента. Затем просто вычислите модуль как обычно.
Как аппроксимация помогает вычислить биномиальный коэффициент по модулю M? Аппроксимации в значительной степени бессмысленны по модулю арифметики. –
Извините, я пропустил часть аппроксимации. – Quixotic
Вот простой пример:
(A * B * C) % N ... is equal to... ((A % N) * (B % N) * (C % N)) % N;
То есть, все, что вам нужно применить модуль для каждого операнда и продукта, или, как только это станет большим числом. И, наконец, модуль должен применяться к общему результату.
С 32-битным int он все равно может вызвать переполнение на 1000000000 * 1000. – ybungalobill
@ ybungalobill: apply '((1000000000% N) * (1000)% N)% N'. – Nawaz
Обратите внимание, что в вопросе модуль равен M, а не N, а приведенный пример, хотя и не простой, составляет около миллиарда. Поэтому '1000000000% N' по-прежнему' 1000000000'. Чтобы избежать переполнения, вам понадобится целочисленный тип размером до N^2 (например, 'long long' или' int64_t', если доступно) –
С 1000000003 = 23 * 307 * 141623 можно вычислить (п выбирает к) по модулю 23 , 307 и 141623, а затем применить китайскую теорию напоминания [1]. При расчете n !, k! и (n-k) !, каждый шаг должен вычислять каждый шаг 23, 307 и 141623 для предотвращения переполнения.
Таким образом, вы должны избегать переполнения даже на 32-битных машинах.
Небольшое улучшение было бы вычислять (n choses k) mod 141623 и 7061 (23 * 307) (редактировать: но может быть немного сложно вычислить обратный модуль 7061, поэтому я бы этого не делал)
Прошу прощения за мой плохой английский.
[1] http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Edit2: Другой потенциально проблема, которую я нашел это при вычислении п! mod 23 (например), вероятно, будет 0, но это не означает, что (n choses k) равно 0 mod 23, поэтому вы должны подсчитать, сколько раз 23 делит n !, (n-k)! и k! перед вычислением (n choses k). Вычисление это легко, p делит n! ровно пол (n/p) + пол (n/p²) + ... раз. Если это произойдет, то 23 делит n! в то же время он делит k! и (nk) !, вы переходите к вычислению (n choses k) mod 23, делящему на каждый каждый раз каждый раз каждый раз. То же самое относится к 307, но не для 141623
Для небольших простых чисел 23 и 307 вы можете использовать http://en.wikipedia.org/wiki/Lucas%27_theorem вместо подсчета полномочий. –
Кажется, [уже в другом месте] (http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690) –