Привет у меня есть проблема в реализации 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;
}
Наконец я получил ошибки в своем коде.
ошибки ….
md
а также co
как без знака долго долгоpow(a,b) % md
….. в pow()
x % md
перед дальнейшей обработкой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;
}
Других решений пока нет …