# 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;

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 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.

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 = 1;

for (int i=1; i<= n; i++) {
fact[i] = (fact[i-1]*i)%p;
}

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

invFact = invFact = 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