在 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屋！