Need help in mod 1000000007 questions

Question

I am weak in mathematics and always get stuck with the problems which require answer modulo some prime no.

eg: (500!/20!) mod 1000000007

I am familiar with BigIntegers but calculating modulo after calculating factorial of 500(even after using DP) seems to take a load of time.

I'd like to know if there's a particular way of approaching/dealing with these kind of problems.

Here is one such problem which I am trying to solve at the moment: http://www.codechef.com/FEB12/problems/WCOUNT

It would really be helpful if someone could direct me to a tutorial or an approach to handle these coding problems. I am familiar with Java and C++.

Procyon

Answer 1

The key to these large-number modulus tasks is not to compute the full result before performing the modulus. You should reduce the modulus in the intermediate steps to keep the number small:

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

You don't need to reduce modulus at every single step. Just do it often enough to keep the number from getting too large.

---

Note that the max value of long is 2^63 - 1. So performing 64 bit multiplications between two positive integer values (i.e. one of the operands is a long) will not overflow long. You can safely perform the remainder operation % afterwards (if that is positive as well) and cast back to an integer when required.

Lardy

thank you for your answer. could you help me with one more doubt. how am I to make sure that eg:31768431*x ( for any x) would not go outside the range of long. – Procyon

If the max value of long is 2^63 - 1, then 1768431 * x will not overflow as long as x < 290331368171. – Lardy

But wouldn't the comparison operation be equally expensive? – Lewan

@Lewan What comparison operations are you referring to? – Lardy

I meant the comparison that would check that the product is less than the overflow range before using the modulus. Basically how would we determine what is often enough? – Lewan

The comparison operation itself is cheap. Determining how many multiplies you can do before you need a reduction is a bit tricker. (Roughly speaking you would need to keep track of the bit-length of the product as it grows.) But you can always default to reducing modulus after every multiply. – Lardy

Answer 2

Start by observing that 500!/20! is the product of all numbers from 21 to 500, inclusive and Next, observe that you can perform modulo multiplication item by item, taking %1000000007 at the end of each operation. You should be able to write your program now. Be careful not to overflow the number: 32 bits may not be enough.

Highkey

Answer 3

I think this could be of some use for you

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 
}

Slavery

Answer 4

In most of the programming competitions, we are required to answer the result in 10^9+7 modulo. The reason behind this is, if problem constraints are large integers, only efficient algorithms can solve them in allowed limited time.

What is modulo operation:
The remainder obtained after the division operation on two operands is known as modulo operation. Operator for doing modulus operation is ‘%’. For ex: a % b = c which means, when a is divided by b it gives the remainder c, 7%2 = 1, 17%3 = 2.
Why do we need modulo:

• The reason of taking Mod is to prevent integer overflows. The largest integer data type in C/C++ is unsigned long long int which is of 64 bit and can handle integer from 0 to (2^64 – 1). But in some problems where the growth rate of output is very high, this high range of unsigned long long may be insufficient. Suppose in a 64 bit variable ‘A’, 2^62 is stored and in another 64 bit variable ‘B’, 2^63 is stored. When we multiply A and B, the system does not give a runtime error or exception. It just does some bogus computation and stores the bogus result because the bit size of result comes after multiplication overflows.

• In some of the problems, to compute the result modulo inverse is needed and this number helps a lot because it is prime. Also this number should be large enough otherwise modular inverse techniques may fail in some situations.
  Due to these reasons, problem setters require to give the answer as a result of modulo of some number N.
  There are certain criteria on which value of N depends:

1. It should just be large enough to fit in the largest integer data type i.e it makes sure that there is no overflow in result.

2. It should be a prime number because if we take mod of a number by Prime the result is generally spaced i.e. the results are very different results in comparison to mod the number by non-prime, that is why primes are generally used for mod.
   10^9+7 fulfills both the criteria. It is the first 10-digit prime number and fits in int data type as well. In fact, any prime number less than 2^30 will be fine in order to prevent possible overflows.
   How modulo is used:
   A few distributive properties of modulo are as follows:
   

3. ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c

4. ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c

5. ( a – b) % c = ( ( a % c ) – ( b % c ) ) % c

6. ( a / b ) % c = ( ( a % c ) / ( b % c ) ) % c
   
   So, modulo is distributive over +, * and – but not over / [Please refer Modular Division for details] NOTE: The result of ( a % b ) will always be less than b. In the case of computer programs, due to the size of variable limitations, we perform modulo M at each intermediate stage so that range overflow never occurs.

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.

Function for finding factorial of a large number using modulo but at different positions.

reference: https://www.geeksforgeeks.org/modulo-1097-1000000007/

Diplo