階乘和分的模數

Question

如何解決(a!/(b! * c!)) % mod。這裏的a!是因子a。

正如(a + b) % mod = (a % mod + b % mod) % mod

我知道計算(a * b) % mod。

但是如何取這種函數的模數呢？

已更新：最好的方法是什麼(a/(b * c)) % mod。 這裏mod是素數。

Answer 1

注意(a!/(b! * c!)) % M等於((a! % M)/((b! % M) * (c! % M))) % M所以實現x! % M：

def modfac(x, M): 
    if x == 0: 
     return 1 
    else: 
     return (modfac(x-1, M)*x)%M 

這可能進行迭代，但它只是一個例子。

，然後使用它：

(modfac(a,M)/(modfac(b,M) * modfac(c,M))) % M