如何计算nCr %m

Question

假设m为not prime，如何计算nCr？

1 <= n, r <= 100000

例如，如果我们有m质数，我们可以做的是fact(n) * invmod(fact(r)) * invmod(fact(n-r))

where invmod(a) = power(a, m-2)

如果m不是质数，该怎么办？

Answer 1

我们知道

C(n,r) = fact(n)/(fact(r)*fact(n-r))

但考虑C(7,5)：

C(7,5) = 7x6x5x4x3x2x1 / (5x4x3x2x1 * 2x1)
       = 7x6 / 2x1

所以想象一下，我们不是做所有的产品，而是用一系列的值：

C(7,5) = product( set(1..7) - set(1..5) ) / product(1..2)

但实际上，我们可以定义一个交叉取消函数，它取一个集合中的项目，并在可能的情况下从第二个集合中取消值：

crossCancel(numeratorSet, denominatorSet) -> 
   remainingNumers, remainingDenoms

这应该给我们留下需要计算模m的最小乘积，但我们可以走得更远。如果我们把剩下的每一项都分成它的因子：

  7x6 / 2
= 7x3x2 / 2

进一步减少将取消2

= 7x3

实际上，我们知道nCr每次都会取消公共产品(5x4..1)，因此我们可以立即将其缩短为

product(set(r+1..n))/product(set(1..n-r))

还可以证明，分母总是会抵消到分子中(因为如果r和n被例如3分开，那么3将在分母中，并且3个连续的数字将在分子中，所以必须取消)，所以我们知道我们总是可以这样做

product(set(factorsOf(r+1 .. n)) - set(1..n-r))

考虑到现在有限的乘积，确定模数m的乘积应该是多少应该是相当简单的。