Coefficient binaire mod10 ^ 9 + 7

introduction

[Une fonction spéciale sur la façon de trouver "trop divisé par 1000000007"! ~ De l'élément inverse au logarithme discret ~](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#5-%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0 -ncr) C'est le code de ** 5. Coefficient binaire nCr ** dans ce document réécrit en Python. (Merci drken toujours)

code

MAX_NUM = 10**6 + 1
MOD = 10**9+7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

Recommended Posts

Coefficient binaire mod10 ^ 9 + 7
[Astuces Python] Somme des coefficients binomiaux, coefficient binomial nCr mod (10 ^ 9 + 7)