需要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.

如：（！20分之500）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.

下面就是这样的一个问题，而我试图解决的时刻： <一href="http://www.$c$cchef.com/FEB12/problems/WCOUNT">http://www.$c$cchef.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.

这篇关于需要MOD 1000000007提问帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！