nCr mod M

 

 

nCr mod M

Given 3 integer N,R and M. You task is to calculate ^NC_R%M.

Input:

The first line of the input contains an integer T denoting the number of test cases.Then T test cases follow. Each test case consists of 3 integers N,R and M.

Output:

For each test case output a single integer representing the value of ^NC_R%M

Constraints :
1<=T<=100
1<=R<=N<=10^9
1<=M<=10^5 where  M is a square free and the largest prime factor of M is <=50.
 

Example:
Input:
3
4 2 28681
3 1 43710
5 3 3655

Output:
6
3
10

Although I have previously solved more than a few nCr mod M problems on this web site, this one is much more difficult for two reasons: (1) M can be less than n and/or r and (2) M is not necessarily prime.

Let us look at 10C8 % 7 (for example).
(10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) / ( (8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) * (2 * 1) ) % 7
(10 % 7) * (9 % 7) * (8 % 7) * (7 % 7) * ,,, * (1 % 7) / ( (8 % 7) * (7 % 7) * ... (1 % 7) * (2%7) * (1%7) )
If we blindly calculate, the (7 % 7) = 0 yields 0 / 0 which is not a good answer.
We could easily divide out the 7 / 7 = 1 in this simple case, but, since n <= 10 ^ 9 we would not be able to divide out all the 7's quickly and we would get a time limit exceeded verdict. So this is why
M < n may present a problem.
Also, if M is not a prime number, we will not be able to find its multiplicative inverse.

The Editorial is correct, but it was a little vague for me, so I will show an example of how to solve
100 C 25 % 30.

The prime factors of 30 are 2, 3 and 5.
We next find 100 C 25 % 2 = which will be called remainder 0
100 C 25 % 3 = which will be called remainder 1
100 C 25 % 5 = which will be called remainder 2

To find each remainder, we use Lucas Theorem where we change 100 and 25 to base 2, 3 and 5
I found this link very helpful to understand Lucas Theorem

 

Hello folks, problem that i am gonna discuss is one of the standard problem that we very usually see in contest and it is as follow. You are given certain combinatoric problem which finally ends up with answer n Cr (n choose r),adding to the constraints since value of n Cr can be very large then you are asked to take modulus of the answer.

Solution to above problem : there are two case, first case when MOD is prime and case two when MOD is not prime, in this post i will be sharing answer to when MOD is prime. To solve above problem we use Lucas Theorem which states as follow.

LUCAS THEOREM

If MOD is a prime number, and N has base MOD representation (aj,...,a1,a0) and r has base MOD representation (bj,...,b1,b0), then (N CHOOSE R) is congruent [mod MOD] to

(N choose R) modulus MOD = ((aj CHOOSE bj)...(a1 CHOOSE b1) (a0 CHOOSE b0)) modulus MOD

Let me make it more clear with example, for instance you have answer as (588 choose 277) % 5, then

                **(588 choose 277) % 5 = ?
                Representation of 588 in base of 5 = 4323
                Representation of 277 in base of 5 = 2102
                Now your answer reduces to = ((4 choose 2)(3 choose 1)(2 choose 0)(3 choose 2)) % 5
                                         = (6 * 3 * 1 * 3) % 5
                                         = 54 % 5
                                         = 4**

Important tip to calculate (aj choose bj) you can pre compute factorial upto MOD-1 and store that in array and hence you can compute (aj choose bj) in O(1) time.

Important observation : their might be certain cases when (aj < bj) in that case simply return 0 as your answer, why ? left for you geek :P

One of the limitation of this theorem is, it works fine when the value of MOD is small if value of MOD is itself large then it become difficult to store factorial of values up to MOD-1. 

 

100 base 2 = 110 0100
25 base 2 = 001 1001 (1 C 0) * (1 C 0) * (0 C 1) * (0 C 1) ... = 1 * 1 * 0 * 0 ... = 0
100 base 3 = 1 0201
25 base 3 = 0 0221 (1 C 0) * (0 C 0) * (2 C 2) * (0 C 2) * (1 C 1) = 1 * 1 * 1 * 0 * 1 = 0
100 base 5 = 400
25 base 5 = 100 (4 C 1) * (0 C 0) * (0 C 0) = 4 * 1 * 1 = 4

Now we finally use the Chinese Remainder Theorem to combine these three results
Ans = sum ( remainder[i] * pp[i] * inv[i]) % M

pp[i] = m / m[i] and inv[i] is the modular multiplicative inverse of pp[i] with respect to m[i]
pp[0] = 30 / 2 = 15 pp[1] = 30 / 3 = 10 pp[2] = 30 / 5 = 6
inv[0] = 15 % 2 = 1 the multiplicative inverse of 1 mod 2 = 1
inv[1] = 10 % 3 = 1 the multiplicative inverse of 1 mod 3 = 1
inv[2] = 6 % 5 = 1 the multiplicative inverse of 1 mod 5 = 1

(Note that multiplicative inverse of 1 mod M will always be 1 for all M that are prime,
but in general, the multiplicative inverse of a mod M rarely equals a when a != 1. )
In general, we can use Extended Euclid to find the multiplicative inverse.

Now back to the Chinese Remainder Theorem ...
ans = ((0 * 15 * 1) + (0 * 10 * 1) + (4 * 6 * 1)) % 30 = 24 % 30 = 24

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
#define ll long long int
ll fact[MAX+1];
void factcal(ll n)
{
    fact[0]=1;
    fact[1]=1;
    for(long long i=2;i<=n;++i)
    {
    fact[i]=((long long)(fact[i-1]%n*i%n))%n;
    }
    return;
}


ll fermat(ll a, ll b,ll m)
{
   
    if(b==0)
    return 1;
    if(b%2==0)
    {
        return ((long long)fermat((long long)(a%m*a%m)%m,b/2,m))%m;
    }else{
        return ((long long)(a%m*fermat(a,b-1,m)%m))%m;
    }
}
ll lucas(ll n, ll r, ll m)
{
   
    if(n<r)
    return 1;
    ll a=fact[n];
    ll b=fact[r];
    ll c=fact[n-r];
    ll inverBC=(long long)(b%m*c%m)%m;
    ll num= ((long long )((a%m)*(fermat(inverBC,m-2,m)%m)))%m;
    return num;
}
ll solve(ll n,ll r,ll m)
{
   
    if(r==0)
    return 1;
    if(n<r)
    return 1;
    return  ((long long)((solve(n/m,r/m,m)%m*lucas(n%m,r%m,m)%m)))%m;
}
int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        ll n,r,m;
        cin>>n>>r>>m;
        factcal(m);
        cout<<solve(n,r,m)<<endl;
    }
    return 0;
}