c++dynamicmodular-arithmeticncr

implementation of nCr and inverse factorial (MODm) for very large numbers


Hi i have problem in implementing nCr MODm in code sprint5 problem. Link to the problem is ...... https://www.hackerrank.com/contests/codesprint5/challenges/matrix-tracing. what I learned yet is I can apply rules of mudular arithmatic to factorial computation and inverse factorial computation and also to computing pow(a,b) MODm.But I don't know what I am missing which is leading to wrong answer. Here is my current code .

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include<math.h>
using namespace std;
const int md = 1000000007;
const int co = 2000020;
unsigned long long int ft[co];

long long int fact(unsigned long long int n)
{   
   return ft[n];
}

void fct(){
    ft[1]=1;
    for(unsigned long long int i = 2;i<=2000020;i++){
        ft[i]=(i*ft[i-1]) % md;
        }
    }

long long int pow(long long int x, long long int n, long long int mod){
    long long int result=1; 
    while(n>0){
        if(n%2 ==1){
            result = (result*x) % mod;
        }
        n= n>>1;
        x= (x*x)% mod;  
    }
    return result;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    unsigned long long int m , n;
    long long result;
    int T;
    fct();
    cin>>T;
    while(T--){
        cin>>m>>n; 
        unsigned long long int mod = md-2;
         result = (fact(m+n-2) * pow( ( fact(m-1) * fact(n-1) ) , mod, md )) % md ;
        cout<<result<<endl;
    }
    return 0;
}

Solution

  • Finally I got the errors in my code.

    errors....

    1. I should use constant variables md and co as unsigned long long int instead of only int
    2. Second error is in algorithm for computing pow(a,b) % md ..... in pow() function, I should first do x % md before processing further because there is probability that x can be passed greater than md .

    current working code is.....

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <map>
    #include<math.h>
    using namespace std;
    const unsigned long long int md = 1000000007; 
    const unsigned long long int co = 2000020;
    unsigned long long int ft[co];
    
    unsigned long long int fact(unsigned long long int n)
    {   
        return ft[n];
    }
    
    void fct(){
        ft[0]=1;
        for(unsigned long long int i = 1;i<=2000020;i++){
            ft[i]=(i*ft[i-1]) % md;
        }
    }
    
    unsigned long long int pow(unsigned long long int x, unsigned long long int n, unsigned long long int mod){
        unsigned long long int result=1; 
        x = x % md;
        while(n>0){
            if(n%2 ==1){
                result = (result*x) % md;
            }
            n= n>>1;
            x= (x*x)% md;   
        }
        return result;
    }
    
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
        unsigned long long int m , n;
        unsigned long long int result;
        int T;
        fct();
        cin>>T;
        while(T--){
            cin>>m>>n; 
            unsigned long long int mod = md-2;   
            result = (fact(m+n-2) * pow( ( fact(m-1) * fact(n-1) ) , mod, md )) % md ;
            cout<<result<<endl; 
        }
    
        return 0;
    }