Combinations (nCr mod p) - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/combinations-ncr

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/combinations-ncr

Repovive

Combinations (nCr mod p) - Algorithm Tutorial | Repovive | Repovive

r

r

function precompute(maxN, mod):
    fact = array of size maxN + 1
    invFact = array of size maxN + 1

    fact[0] = 1
    for i from 1 to maxN:
        fact[i] = (fact[i-1] * i) mod mod

    invFact[maxN] = modInverse(fact[maxN], mod)
    for i from maxN - 1 down to 0:
        invFact[i] = (invFact[i+1] * (i+1)) mod mod

    return (fact, invFact)

function nCr(n, r, fact, invFact, mod):
    if r < 0 or r > n:
        return 0
    return (fact[n] * invFact[r] mod mod) * invFact[n-r] mod mod

Combinations (nCr mod p) Algorithm Tutorial

Learn

Binomial Coefficient (nCr mod p)

Practice this Algorithm

Related Algorithms