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.

 

1<=T<=100
1<=R<=N<=10^16
M=10^6+3

Example:

Input:
3
4 2 1000003
3 1 1000003
5 3 1000003

Output:
6
3
10

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

 

#include<bits/stdc++.h>
using namespace std;

#define hell 1000000007
#define ll long long
#define MAX 1000003

ll dp[MAX+1];

void fact(ll p)
{
    dp[0]=1;
    for(int i=1; i<=MAX; i++)
    {
        dp[i]=((long long)(i%p*dp[i-1]%p))%p;
    }
    return;
}

ll fermat(ll a,ll b,ll p)
{
    if(b==0)
    {
    return 1;
    }
   
    if(b%2==0)
    {
    return fermat((long long)(a%p*a%p)%p,b/2,p)%p;
    }
    else
    {
    return (a%p*fermat(a,b-1,p)%p)%p;
    }
   
}


ll lucas(ll n, ll r, ll p)
{
   
    if(n < r)
    {
        return 0;
    }
    ll a = dp[n];
    ll b = dp[r];
    ll c = dp[n-r];
    ll den = ((long long)(b%p*c%p))%p;
   
    ll num = ((long long)a%p*fermat(den,p-2,p)%p)%p;
   
   
    return num;
   
}

ll solve(ll n, ll r, ll p)
{
    if(r==0)
    {
        return 1;
    }
    if(n < r)
    {
        return 0;
    }
    ll lastn = n%p;
    ll lastr = r%p;
   
    return ((long long)(solve(n/p,r/p,p)%p)*(lucas(lastn,lastr,p)%p))%p;
}

int main()
{
    int t;
    cin>>t;
    fact(MAX);
   
    while(t--)
    {
        ll n,r,p;
        cin >> n >> r >> p;
        cout << solve(n,r,p) <<endl;
    }
    return 0;
}