Нужна помощь в мод 1000000007 вопросов

Question

Я слаб в математике и всегда зацикливаюсь на проблемах, которые требуют ответа по модулю некоторого простого числа.

например: (500! / 20!) Мод 1000000007

Я знаком с BigIntegers, но вычисление по модулю после вычисления факториала 500 (даже после использования DP), похоже, требует много времени.

Я бы хотел знать, существует ли какой-то особый способ подхода / решения таких проблем.

Вот одна такая проблема, которую я сейчас пытаюсь решить: http://www.codechef.com/FEB12/problems/WCOUNT

Было бы действительно полезно, если бы кто-то мог направить меня к учебнику или подходу для решения этих проблем кодирования. Я знаком с Java и C ++.

Answer 1

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

500! / 20! = 21 * 22 * 23 * ... * 500

21 * 22 * 23 * 24 * 25 * 26 * 27 = 4475671200

4475671200 mod 1000000007 = 475671172
475671172 * 28 mod 1000000007 = 318792725
318792725 * 29 mod 1000000007 = 244988962
244988962 * 30 mod 1000000007 = 349668811

...

 31768431 * 500 mod 1000000007 = 884215395

500! / 20! mod 1000000007 = 884215395

Вам не нужно уменьшать модуль на каждом шаге.Просто делайте это достаточно часто, чтобы число не становилось слишком большим.

---

Обратите внимание, что максимальное значение long равно 2 ^ 63 - 1. Таким образом, выполняется 64-битное умножение между двумя положительными целыми значениями (т.е. один из операндов long) не будет переполнен long.Вы можете безопасно выполнить оставшуюся операцию % впоследствии (если она также является положительной) и при необходимости привести ее к целому числу.

Answer 2

Начните с наблюдения, что 500!/20! - это произведение всех чисел от 21 до 500 включительно, и далее, обратите внимание, что вы можете выполнять умножение по модулю на элемент, беря %1000000007 в конце каждой операции. Вы должны быть в состоянии написать свою программу сейчас. Будьте осторожны, чтобы не переполнить число: 32 бита может быть недостаточно.

Answer 3

Я думаю, что это может быть полезным для вас

for(mod=prime,res=1,i=20;i<501;i++)
{
res*=i; // an obvious step to be done 
if(res>mod) // check if the number exceeds mod
res%=mod; // so as to avoid the modulo as it is costly operation 
}