реализация nCr и обратного факториала (MODm) для очень больших чисел

Привет, у меня проблема с реализацией nCr MODm в коде sprint5. Ссылка на задачу: ...... https://www.hackerrank.com/contests/codesprint5/challenges/matrix-tracing. что я еще узнал, так это то, что я могу применять правила мудулярной арифматики к факторным вычислениям и обратным факторным вычислениям, а также к вычислению pow(a,b) MODm. Но я не знаю, что мне не хватает, что приводит к неправильному ответу. Вот мой текущий код.

#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;
}

c++ dynamic modular-arithmetic ncr
person Tushar    schedule 22.01.2014    source источник
comment
Ваша функция fact возвращается в первой строке, поэтому большая ее часть не будет выполнена.   -  person interjay    schedule 22.01.2014
comment
нет, это просто функция fct(), которая предварительно вычисляет факториалы, которые понадобятся в будущем.   -  person Tushar    schedule 22.01.2014
comment
Тогда почему весь код в fact там? Если он не предназначен для выполнения, удалите его из вопроса.   -  person interjay    schedule 22.01.2014
comment
На самом деле функция получения значений из массива ft[] уже вычислена функцией fct().   -  person Tushar    schedule 22.01.2014
comment
Это потому, что я пробовал обе вещи, вычисляя, когда это было необходимо, а затем заменяя их предварительными вычислениями .... которые работали быстрее.   -  person Tushar    schedule 22.01.2014
comment
Я надеялся, что вы поможете мне понять, сделал ли я что-то не так при реализации этой вещи.   -  person Tushar    schedule 22.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

Наконец я получил ошибки в моем коде.

ошибки....

  1. Я должен использовать постоянные переменные md и co как unsigned long long int, а не только int
  2. Вторая ошибка заключается в алгоритме вычисления pow(a,b) % md ..... в функции pow() я должен сначала выполнить x % md перед дальнейшей обработкой, потому что есть вероятность, что x может быть передано больше, чем md .

текущий рабочий код.....

#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;
}
person Tushar    schedule 22.01.2014