需要帮助mod 1000000007 [英] Need help in mod 1000000007

问题描述

我遇到了一个问题，我需要计算一下：

（（500！）/（20！x20！x20！x20！ ..））mod 1000000007

我理解如何计算500！％1000000007但我不知道如何分布该运算符。

我目前正在尝试编写一个代码，用分子通过其因子取消分母。但我不知道这是否是一个很好的方法。

我只需要一个数学方法解决这些问题（mod1000000007），因为他们经常遇到

解决方案

方法1：

想想你将如何计算 500！ /（20！* 20！* 20！* ...）

不要将所有东西加倍， 。你的分裂在中间。方法2：

p> 整数因式分解 500！和 20！。然后减去素质因子 20！ * 20！ * $ 500！。

$

b $ b

然后通过将剩余因子乘以一起来重建数字。 （同时采用模数来保持数字不变大）

方法3：

如果 1000000007 （或任何模数）是素数，您可以使用模逆。

计算 20！ mod 1000000007 。然后计算它的模逆，并将它乘以 500！ mod 1000000007 。

I'm stuck in a problem in which I need to calculate something like:

((500!)/(20!x20!x20!x20!...)) mod 1000000007

I understand how to calculate 500!%1000000007 but I am not sure on how to distribute that operator in division.

I am currently trying to write a code which cancels the denominators by its numerator by its factors. But I am not sure if it is a good approach to this.

I just need a mathematical way of solving these kind of problems(mod1000000007) as they are regularly encountered in programming competitions and would help me to prepare for Google Code Jam.

解决方案

Method 1:

Think of how you would compute 500! / (20! * 20! * 20! * ...) normally.

Don't multiply everything out and divide at the end. Do your divisions in the middle. Then combine this with the modulus reductions from your previous question.

Method 2:

Prime factorize 500! and 20!. Then subtract out the prime factors of 20! * 20! * 20! (or how ever many of them you have) from the prime factors of 500!.

Then rebuild the number by multiplying back the remaining factors together. (while taking modulus along the way to keep the number from getting large)

Method 3:

If 1000000007 (or whatever modulus) is prime, you can do divisions using the modular inverse.

Compute 20! mod 1000000007. Then compute it's modular inverse and multiply it into 500! mod 1000000007.

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