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++.

Solution 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.

Solution 2

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 
}

Solution 3

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.

Comments

[daerty0153]

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.

[Mysticial]

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

[nikhil]

But wouldn't the comparison operation be equally expensive?

[Mysticial]

@nikhil What comparison operations are you referring to?

[nikhil]

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?

[Mysticial]

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.