如何計算nCr％m

Question

假設m是not prime如何計算nCr？

1 <= n, r <= 100000

一樣，如果我們有m總理，我們能做的就是fact(n) * invmod(fact(r)) * invmod(fact(n-r))

其中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) 

但事實上，我們可以定義一個交叉取消函數，它將一個項目中的項目取消並取消val從第二組在可能的UE：

crossCancel(numeratorSet, denominatorSet) -> 
    remainingNumers, remainingDenoms 

這應該留給我們這就需要計算模m最小的產品，但是我們可以走得更遠。如果我們每個其餘項目拆分成它的因素：

7x6/2 
= 7x3x2/2 

進一步減少取消2S

= 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應該是。