Modular Multiplicative Inverse and Modular Combinatorics (nCr % prime) in C++

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. Written as:

which is the shorthand way of writing the statement that the remainder after dividing ax by the integer m is 1.

Finding the modular inverse in O(m)

The problem is to compute the modular inverse for every number in the range [1, m-1]. We denote the modular inverse of i by inv[i]. Then for i>1 the following equation is valid:

Implementation in C++

    inv[1] = 1;

    for (int i=2; i<= n; i++) {
        inv[i] = ((m - (m/i))*inv[m%i])%m;
    }

Proof

We have:

m \bmod i = m - \left\lfloor \frac{m}{i} \right\rfloor \cdot i

Taking both sides modulo m yields:

m \bmod i \equiv - \left\lfloor \frac{m}{i} \right\rfloor \cdot i \mod m

Multiply both sides by  i^{-1} \cdot (m \bmod i)^{-1} yields

(m \bmod i) \cdot i^{-1} \cdot (m \bmod i)^{-1} \equiv -\left\lfloor \frac{m}{i} \right\rfloor \cdot i \cdot i^{-1} \cdot (m \bmod i)^{-1} \mod m,

which simplifies to:

i^{-1} \equiv -\left\lfloor \frac{m}{i} \right\rfloor \cdot (m \bmod i)^{-1} \mod m,

Computing ⁿC_r % prime

We know that:

nCr =  n! / ((r!) x (n-r)!) 
or
nCr =  factorial(n) / (factorial(r) x factorial(n-r))

Now, using modular inverse, we could write

nCr % p = (factorial[n]*modInverse(factorial[r]) % p *
               modInverse(factorial[n-r]) % p) % p;

Here modInverse() means modular inverse under modulo p.

This is helpful in computing nCr % prime when both n and r are large. Since computing n! and r! will cause Integer overflow.

Code Implementation

//
//  main.cpp
//  Modular Combinatorics
//
//  Created by Himanshu on 18/02/22.
//

#include <iostream>
#define p 1000000007
using namespace std;
typedef long long ll;

void precompute (int n, ll fact[], ll inv[], ll invFact[]) {
    fact[0] = 1;
    
    for (int i=1; i<= n; i++) {
        fact[i] = (fact[i-1]*i)%p;
    }
    
    inv[1] = 1;
    for (int i=2; i<= n; i++) {
        inv[i] = ((p - (p/i))*inv[p%i])%p;
    }
    
    invFact[0] = invFact[1] = 1;
       
    for (int i=2; i<= n; i++) {
        invFact[i] = (invFact[i-1]*inv[i])%p;
    }
}


ll computeCombinatorics (int n, int r, ll fact[], ll inv[], ll invFact[]) {
    ll ans = (((fact[n]*invFact[r])%p)*(invFact[n-r]%p))%p;
    return ans;
}

int main (int argc, const char * argv[]) {
    int n = 100000;
    int r = 500;
    
    ll *fact = new ll[n]();
    ll *inv = new ll[n]();
    ll *invFact = new ll[n]();
    
    precompute(n, fact, inv, invFact);
    cout<<computeCombinatorics(n, r, fact, inv, invFact)<<endl;
    
    return 0;
}

Output

115855765

Time Complexity: O(n)

Here’s a working example: Ideone

References:
Modulo Inverse
Compute nCr % p (Using Fermat Little Theorem)