模组需要帮助1000000007问题

我的数学能力很弱，总是遇到需要回答模数的问题。模组需要帮助1000000007问题

如：（！500/20）MOD 1000000007

我熟悉BigIntegers但（即使使用DP之后）计算的500阶乘后计算模似乎需要很长时间负荷。

我想知道是否有特定的方法来处理这类问题。

这里是我正努力在目前解决一个这样的问题： http://www.codechef.com/FEB12/problems/WCOUNT

这真的会是有益的，如果有人可以直接我的教程或处理这些编码问题的方法。我熟悉Java和C++。

来源

2012-02-07 daerty0153

这些大数模量任务的关键不是在执行模数之前计算完整结果。 你应该减少中间步骤的模量，以保持一些小：

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。之后您可以安全地执行余下的操作%（如果这也是肯定的），并在需要时转换回整数。

来源

2012-02-07 00:09:00 Mysticial

感谢您的回答。你能否再帮助我一个疑问。我如何确保例如：31768431 * x（对于任何x）不会超出long范围。 – daerty0153 2012-02-07 00:12:48

如果long的最大值是2^63-1，那么只要'x <290331368171'，'1768431 * x'就不会溢出。 – Mysticial 2012-02-07 00:15:22

但是，比较操作不会同样昂贵吗？ – nikhil 2012-07-02 14:38:46

首先观察500!/20!是从21到500的所有数字的乘积（包含端点）。接下来，观察您可以逐项执行模乘法，在每个操作结束时执行%1000000007。你现在应该可以编写你的程序。注意不要溢出数字：32位可能不够。

来源

2012-02-07 00:10:13 dasblinkenlight

我认为这可能是一些使用的为您

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 
}

来源

2013-03-22 10:22:08 MissingNumber

模组需要帮助1000000007问题

回答

相关问题