#include <cstdio>
#define MOD 1000000007
int powmod(int base, int expo){
if(expo==0)
return 1;
else if(expo&1)
return (long long)base*powmod(base, expo-1)%MOD;
else{
int root=powmod(base, expo>>1);
return (long long)root*root%MOD;
}
}
int inverse(int x){
return powmod(x, MOD-2);
}
void init(){
fact[0]=1;
for(int i=1; i<=5000; i++)
fact[i]=(long long)i*fact[i-1]%MOD;
invfact[5000]=inverse(fact[5000]);
for(int i=5000; i>0; i--)
invfact[i-1]=(long long)i*invfact[i]%MOD;
}
int nCr(int n, int r){
if(r>n || r<0)
return 0;
return (long long)((long long)fact[n]*invfact[r]%MOD)*invfact[n-r]%MOD;
}
int main(){
init();
int N, K;
while(scanf("%d %d", &N, &K) && (N||K)){
print("%d",nCr(N,K));
}
}
This is code for calculating binomial cofficient = fact(n)/fact(n-r)*fact(r)
value of fact(r)*fact(n-r) lead to overflow so in this code they use a method
of calculating inverse of fact. i could not able to understand how inverse
function work please explain.
Thanks.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UPQyVx70SbkJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
