It's a fact from number theory that
x * (x^(M-2)) = 1 (mod M)
if M is prime. So x^(M-2) is the multiplicative inverse of x (mod
M). It follows by identities of modulo arithmetic that
n!/(r!(n-r)!) = n! * inv(r!) * inv( (n-r)! ) (mod M)
This is what the code is computing. A basic number theory book will
cover this stuff in the early chapters.
On Mar 5, 5:13 am, amrit harry <dabbcomput...@gmail.com> wrote:
> #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 post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
