需要帮助mod 1000000007的问题

Question

我在数学方面很弱,总是遇到需要回答模数的问题.

例如:(500!/ 20!)mod 1000000007

我熟悉BigIntegers但计算因子500后计算模数(即使在使用DP之后)似乎需要花费一些时间.

我想知道是否有一种接近/处理这类问题的特殊方式.

这是我目前要解决的一个问题:http: //www.codechef.com/FEB12/problems/WCOUNT

如果有人可以指导我处理这些编码问题的教程或方法,那将会非常有用.我熟悉Java和C++.

Answer 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位乘法(即其中一个操作数是a long)将不会溢出long.之后您可以安全地执行余数运算%(如果这也是正数),并在需要时转换回整数.

Answer 2

首先观察这500!/20!是21到500之间所有数字的乘积,然后观察您可以逐项执行模数乘法,%1000000007在每个操作结束时进行.你现在应该可以编写程序了.注意不要溢出数字:32位可能不够.

Answer 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 
}