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++.
7 are prime numbers and 1000000007 is the biggest one that fits in 32-bit integer. Since prime numbers are used to calculate hash (by finding the remainder of the division by prime), 1000000007 is good for calculating 32-bit hash.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With