在 mod 1000000007 问题中需要帮助 [英] Need help in mod 1000000007 questions
问题描述
我在数学方面很弱,总是被需要以一些素数为模数的答案的问题卡住.
I am weak in mathematics and always get stuck with the problems which require answer modulo some prime no.
例如:(500!/20!) mod 1000000007
eg: (500!/20!) mod 1000000007
我熟悉 BigIntegers,但是在计算 500 的阶乘之后计算模数(即使在使用 DP 之后)似乎需要很长时间.
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.
这是我目前正在尝试解决的一个这样的问题:http://www.codechef.com/FEB12/problems/WCOUNT
Here is one such problem which I am trying to solve at the moment: http://www.codechef.com/FEB12/problems/WCOUNT
如果有人能指导我学习处理这些编码问题的教程或方法,那真的很有帮助.我熟悉 Java 和 C++.
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++.
推荐答案
这些大数模数任务的关键是在执行模数之前不要计算完整结果.您应该在中间步骤中降低模数以保持数量较小:
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.
注意 long
的最大值是 2^63 - 1.因此在两个正整数值之间执行 64 位乘法(即操作数之一是 long
) 不会溢出 long
.之后您可以安全地执行余数运算 %
(如果它也是正数)并在需要时转换回整数.
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.
这篇关于在 mod 1000000007 问题中需要帮助的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!