如何nCr的计算模1000000007当n＆LT; 400000？ [英] How to calculate nCr modulo 1000000007 when n < 400000?

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/4638988/how-can-we-compute-n-choose-k-modulus-a-prime-number-without-overflow">How我们可以计算ň取K模量的素数没有溢出？
  变更路径计数的矩形
   nCr的模p为大n和p为素

Possible Duplicate:
How can we compute N choose K modulus a prime number without overflow?
Modified paths Counting in a Rectangle
nCr mod p for large n and p is prime

是不允许的40万* 40万整数一个二维数组，因此动态规划是不是一个不错的选择。无论是将矩阵乘法的帮助，因为这将需要40万* 40万的2-D阵列的存储。卢卡斯定理是没有用的，因为这里的每个整数小于1000000007，所以计算的次数将是相同的。我需要计算：

A 2-D array of 400000 * 400000 integers is not allowed, hence dynamic programming is not an option here. Neither will matrix multiplication help, since it will require storing of 400000 * 400000 2-D array. The Lucas theorem is of no use here since every integer is less than 1000000007, so the number of computations will be the same. I need to calculate:

   SUM( (l+i)Ci * (m + n - i)Cm ) 

其中，我的取值范围为0至X; X，L，M，N 是固定的。什么是最有效的算法来做到这一点？

where i ranges from 0 to X; X,l,m,n are fixed. What would be the most efficient algorithm to do so?

推荐答案

使用模逆。 （A / B）模p =（A * B ^ -1）模p

我们有：

nCr = n! / (r!*(n - r)!) = n! * (r!*(n - r)!)^-1 (mod p)

有关 P 素，任何数字的倒数 X MOD P 是 X ^（P - 2）。模p （欧拉定理）

For p prime, the inverse of any number x mod p is x^(p - 2) mod p (Euler's Theorem).

这篇关于如何nCr的计算模1000000007当n＆LT; 400000？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！