Нужна помощь в моде 1000000007 вопросов
Я слаб в математике и всегда зацикливаюсь на проблемах, которые требуют ответа по модулю некоторого простого числа.
например: (500!/20!) мод 1000000007
Я знаком с BigIntegers, но вычисление по модулю после вычисления факториала 500(даже после использования DP), кажется, занимает много времени.
Я хотел бы знать, есть ли особый способ подхода / решения таких проблем.
Вот одна из таких проблем, которую я сейчас пытаюсь решить: http://www.codechef.com/FEB12/problems/WCOUNT
Было бы действительно полезно, если бы кто-то мог направить меня к учебнику или подходу для решения этих проблем кодирования. Я знаком с Java и C++.
4 ответа
Ключ к этим задачам по модулю большого числа не состоит в том, чтобы вычислить полный результат перед выполнением модуля. Вы должны уменьшить модуль на промежуточных этапах, чтобы число оставалось небольшим:
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, Вы можете безопасно выполнить оставшуюся операцию % потом (если это тоже положительно) и при необходимости возвращает обратно к целому числу.
Начните с наблюдения, что 500!/20! это произведение всех чисел от 21 до 500 включительно и далее, обратите внимание, что вы можете выполнять умножение по модулю элемент за элементом, принимая %1000000007 в конце каждой операции. Вы должны быть в состоянии написать свою программу сейчас. Будьте осторожны, чтобы не переполнить число: 32 бита может быть недостаточно.
Я думаю, что это может быть полезным для вас
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
}
На большинстве соревнований по программированию от нас требуется отвечать по модулю 10 ^ 9 + 7. Причина этого в том, что если ограничения задачи являются большими целыми числами, только эффективные алгоритмы могут решить их за отведенное ограниченное время.
Что такое операция по модулю:
остаток, полученный после операции деления двух операндов, известен как операция по модулю. Оператор для выполнения операции модуля - "%". Например: a% b = c, что означает, что когда a делится на b, получается остаток c, 7%2 = 1, 17%3 = 2.
Зачем нам нужен модуль по модулю:
Причина использования Mod - предотвратить целочисленное переполнение. Самый большой целочисленный тип данных в C / C++ - это unsigned long long int, который имеет 64-битный формат и может обрабатывать целые числа от 0 до (2 ^ 64-1). Но в некоторых задачах, где темп роста выпуска очень высок, этого большого диапазона длинных длинных длин без знака может быть недостаточно. Предположим, что в 64-битной переменной «A» хранится 2 ^ 62, а в другой 64-битной переменной «B» - 2 ^ 63. Когда мы умножаем A и B, система не выдает ошибку или исключение во время выполнения. Он просто выполняет некоторые фиктивные вычисления и сохраняет фиктивный результат, потому что размер результата в битах определяется после переполнения умножения.
В некоторых задачах для вычисления результата по модулю обратного требуется, и это число очень помогает, потому что оно простое. Также это число должно быть достаточно большим, иначе в некоторых ситуациях модульные обратные методы могут не сработать.
По этим причинам, проблема сеттеры требуют , чтобы дать ответ как результат по модулю некоторого числа N .
Существуют определенные критерии, от которых зависит значение N:
Он должен быть достаточно большим, чтобы поместиться в самый большой целочисленный тип данных, т.е. он должен гарантировать отсутствие переполнения в результате.
Это должно быть простое число, потому что если мы возьмем модификация числа на простое число, результат обычно будет разнесен, т.е. результаты будут сильно отличаться по сравнению с модификацией числа на непростое число, поэтому для модификации обычно используются простые числа.
10 ^ 9 + 7 удовлетворяет обоим критериям. Это первое 10-значное простое число, которое также подходит для типа данных int. Фактически, любое простое число меньше 2 ^ 30 подойдет для предотвращения возможных переполнений.
Как используется модуль modulo:
Вот несколько распределительных свойств модуля modulo:(a + b)% c = ((a% c) + (b% c))% c
(a * b)% c = ((a% c) * (b% c))% c
(a - b)% c = ((a% c) - (b% c))% c
(a / b)% c = ((a% c) / (b% c))% c
Итак, по модулю распределяется над +, * и -, но не над / [Пожалуйста, обратитесь к модульному подразделению для подробностей] ПРИМЕЧАНИЕ: результат of (a% b) всегда будет меньше b. В случае компьютерных программ, из-за размера переменных ограничений, мы выполняем по модулю M на каждом промежуточном этапе, чтобы никогда не происходило переполнение диапазона.
Example: a = 145785635595363569532135132 b = 3151635135413512165131321321 c = 999874455222222200651351351 m = 1000000007 Print (a*b*c)%m. Method 1: First, multiply all the number and then take modulo: (a*b*c)%m = (459405448184212290893339835148809 515332440033400818566717735644307024625348601572) % 1000000007 a*b*c does not fit even in the unsigned long long int due to which system drop some of its most significant digits. Therefore, it gives the wrong answer. (a*b*c)%m = 798848767 Method 2: Take modulo at each intermediate steps: i = 1 i = (i*a) % m // i = 508086243 i = (i*b) % m // i = 144702857 i = (i*c) % m // i = 798848767 i = 798848767 Method 2 always gives the correct answer.
Функция для нахождения факториала большого числа по модулю, но в разных позициях.
ссылка: https://www.geeksforgeeks.org/modulo-1097-1000000007/