Modulo multiplicative inverse

CodeChef-DSA-learners
,
1

Problem Code - BINXOR.
To find nCr why do we need to find the modulo multiplicative inverse of (n-r)! & r!;

2

^nC_r \ \text{mod} \ p = \dfrac{n!}{r!(n-r)!} \ \text{mod} \ p = [(n! \ \text{mod} \ p) \times (r!^{-1} \ \text{mod} \ p) \times ((n-r)!^{-1} \ \text{mod} \ p)] \ \text{mod} \ p
This is to find the modulo multiplicative inverse in general. ^nC_r can be very large. So it’s a good idea to bring everything to the numerator and then individually mod everything.

For a better idea, solve this problem.

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

using namespace std;
const long long s = 1e6+1, mod = 1e9+7;

long long fast(long long x, long long y, long long p)
{
    x %= p;
    long long res = 1;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y >>= 1;
        x = (x * x) % p;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector <long long> f(s);
    f[0] = 1;
    for (int i = 1; i < s; ++i) f[i] = (i*f[i-1]) % mod;
    int t;
    cin >> t;
    while (t--)
    {
        long long n, r;
        cin >> n >> r;
        cout << (((f[n]*fast(f[r], mod-2, mod))%mod)*(fast(f[n-r], mod-2, mod)%mod))%mod << '\n';
    }
}

You can also see this nice guide.

3

Thanks mate!
Really helpful!