0

我想有效地计算 ((X+Y)!/(X!Y!))% P (P 就像 10^9+7)

这个讨论给出了一些关于在除法上分配模数的见解。我担心的是，一个数字不一定总是存在模逆。基本上，我正在寻找解决问题的代码实现。

对于乘法，它非常简单：

public static int mod_mul(int Z,int X,int Y,int P)
{
// Z=(X+Y) the factorial we need to calculate, P is the prime
long result = 1;
while(Z>1)
  {
    result = (result*Z)%P
    Z--;
  }
return result;
}

我也意识到许多因素可以在除法中被取消（在取模之前），但如果除数的数量增加，那么我发现很难有效地提出一个除法算法。（循环遍历 List(factors(X)+factors(Y)...) 以查看哪个除以当前的分子乘数）。

编辑：我不想使用 BigInt 解决方案。

是否有任何基于 java/python 的解决方案或任何标准算法/库来取消因素（如果逆选项不是完全证明）或解决此类问题。

4

3 回答 3

3

((X+Y)!/(X!Y!))(X+Y)-choose-X是二项式系数 ( )的一种低级拼写方式。虽然您在问题中没有这么说，但代码中的注释暗示这P是主要的。将这两者放在一起，卢卡斯定理直接适用： http ://en.wikipedia.org/wiki/Lucas%27_theorem 。

这给出了一个基于 和 的基本表示的非常简单的P算法。是否需要是不可能猜测的，因为你没有对你的论点给出任何限制，除此之外它们是s。请注意，如果例如大于最大值的平方根，您的示例代码可能根本不起作用（因为可能会溢出）。X+YXBigIntsintmod_mulPintresult * Z

于 2014-01-18T07:42:10.260 回答
3

这是二项式系数 - C(x+y,x)。

你可以用不同的方式计算它C(n,m)=C(n-1,m)+C(n-1,m-1)。

如果你对时间复杂度 O(x*y) 没问题，代码会简单得多。

http://en.wikipedia.org/wiki/Combination

于 2014-01-18T07:42:16.553 回答
3

因为您需要的是一种有效地做到这一点的方法：-

  1. C(n,k) = C(n-1,k) + C(n-1,k-1)

  2. 使用动态规划计算自下而上的效率

  3. C(n,k)%P = ((C(n-1,k))%P + (C(n-1,k-1))%P)%P

    因此 F(n,k) = (F(n-1,k)+F(n-1,k-1))%P

另一种更快的方法：-

  1. C(n,k) = C(n-1,k-1)*n/k

  2. F(n,k) = ((F(n-1,k-1)*n)%P*inv(k)%P)%P

inv(k)%P 表示 k 的模逆。

注意：- 尝试评估C(n,n-k) if (n-k<k) because nC(n-k) = nCk

于 2014-01-18T08:36:08.100 回答