我的数学能力很弱，总是陷入那些需要以模素数为模的答案的问题。
例如：（500！/ 20！）mod 1000000007
我对BigIntegers很熟悉，但是在计算500的阶乘（即使使用DP之后）之后计算模数似乎要花费大量时间。
我想知道是否存在解决此类问题的特殊方法。
这是我目前正在尝试解决的一个此类问题：http : //www.codechef.com/FEB12/problems/WCOUNT
如果有人可以引导我学习解决这些编码问题的教程或方法，那将非常有帮助。我熟悉Java和C ++。
这些大量模量任务的关键是在执行模量之前不计算全部结果。 您应该在中间步骤中减小模数以保持数量小：
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。因此，在两个正整数值（即操作数之一是a long）之间执行64位乘法运算不会溢出long。之后，您可以安全地执行余数运算%（如果也为正数），并在需要时转换为整数。
long
%
