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

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

например: (500!/20!) mod 1000000007

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

Я хотел бы знать, есть ли какой-то конкретный способ приблизиться к этим проблемам.

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

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

Ответы

Ответ 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. Вы можете безопасно выполнить оставшуюся операцию % после этого (если это тоже положительно) и при необходимости вернуть обратно к целому числу.

Ответ 2

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

Ответ 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 
}