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

Question

Привет, у меня есть проблема при реализации 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; 
} 

Answer 1

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

ошибки ....

1. я должен использовать постоянные переменные md и co, как неподписанный долго долго 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; 
}