Problem Code - BINXOR.
To find nCr why do we need to find the modulo multiplicative inverse of (n-r)! & r!;
^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.
Thanks mate!
Really helpful!