在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 * ... * 50021 * 22 * 23 * 24 * 25 * 26 * 27 = 44756712004475671200 mod 1000000007 = 475671172475671172 * 28 mod 1000000007 = 318792725318792725 * 29 mod 1000000007 = 244988962244988962 * 30 mod 1000000007 = 349668811... 31768431 * 500 mod 1000000007 = 884215395500! / 20! mod 1000000007 = 884215395您无需在每一步都减少模量。只要经常做就足以防止数量过大。请注意，的最大值long为2 ^ 63-1。因此，在两个正整数值（即其中一个操作数为a long）之间执行64位乘法运算不会溢出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&nbsp;if(res>mod) // check if the number exceeds modres%=