Modular Inversion technique

1. The general formula of nCr is ( n*(n-1)(n-2) … *(n-r+1) ) / (r!). We can directly use this formula to find nCr. But that will overflow out of bound. We need to find nCr mod m so that it doesn’t overflow. We can easily do it with modular arithmetic’s formula.

for the n*(n-1)(n-2)(n-r+1) part we can use the formula, (ab) mod m = ((a % m) * (b % m)) % m

1. and for the 1/r! part, we need to find the modular inverse of every number from 1 to r. Then use the same formula above with a modular inverse of 1 to r. We can find modular inverse in O(r) time using the formula,

inv[1] = 1 inv[i] = − ⌊m/i⌋ * inv[m mod i] mod m To use this formula, m has to be a prime.

In the practice problem, we need to show the answer with modulo 1000000007 which is a prime.

So, this technique will work.

• C++
• Java
• Python3
• C#

`// C++ program for the above approach`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`// Function to find binomial`

`// coefficient`

`int` `binomialCoeff(` `int` `n, ` `int` `r)`

`{`

` ` `if` `(r > n)`

` ` `return` `0;`

` ` `long` `long` `int` `m = 1000000007;`

` ` `long` `long` `int` `inv[r + 1] = { 0 };`

` ` `inv[0] = 1;`

` ` `if` `(r+1>=2)`

` ` `inv[1] = 1;`

` ` `// Getting the modular inversion`

` ` `// for all the numbers`

` ` `// from 2 to r with respect to m`

` ` `// here m = 1000000007`

` ` `for` `(` `int` `i = 2; i <= r; i++) {`

` ` `inv[i] = m - (m / i) * inv[m % i] % m;`

` ` `}`

` ` `int` `ans = 1;`

` ` `// for 1/(r!) part`

` ` `for` `(` `int` `i = 2; i <= r; i++) {`

` ` `ans = ((ans % m) * (inv[i] % m)) % m;`

` ` `}`

` ` `// for (n)*(n-1)*(n-2)*...*(n-r+1) part`

` ` `for` `(` `int` `i = n; i >= (n - r + 1); i--) {`

` ` `ans = ((ans % m) * (i % m)) % m;`

` ` `}`

` ` `return` `ans;`

`}`

`/* Driver code*/`

`int` `main()`

`{`

` ` `int` `n = 5, r = 2;`

` ` `cout << ` `"Value of C("` `<< n << ` `", "` `<< r << ` `") is "`

` ` `<< binomialCoeff(n, r) << endl;`

` ` `return` `0;`

`}`

Output

Value of C(5, 2) is 10

Time Complexity: O(n+k)

Auxiliary Space: O(k)