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:

ax \equiv 1 \pmod{m},

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] = ((mod - (mod/i))*inv[mod%i])%mod;
    }
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 nCr % 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.

Code Implementation in C++
//
//  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;
}

Time Complexity: O(n)

Here’s a working example:
https://ideone.com/Nmzddv

References:

https://cp-algorithms.com/algebra/module-inverse.html
https://www.geeksforgeeks.org/compute-ncr-p-set-3-using-fermat-little-theorem/

Leave a Reply

Your email address will not be published.