[Solved]: Compute 'permutation' like problem with modulo

Problem Detail: 

Say, I have some permutation or combination formula like this,
$$\frac{n!}{(n-r)!r!},$$ and I want to $\bmod$ the result with some big prime ($10^9+7$ for example).

I already tried with modular operation and multiplicative inverse but failed (I don't quite understand them). Can someone give me some example in code so I can grasp the idea? (I prefer C).

Asked By : Nightmare

Answered By : ratchet freak

The formula $\frac{n!}{(n-r)!r!}$ can also be written as $$\prod^n_{i=r+1}{\frac{i}{n-i}}$$

You can rearrange the numerators so you never need to modulo divide (for each $i$ there is a $n-i'$ that divides it)

BigInt* res=new BigInt(1); bool flags[r]=//all false //flags is there to make sure we don't divide twice for(int i=r+1;r<=n;i++) {     int num = i;     for(int j=0;j<r;j++)     {         if(!flag[j] && num%j==0)         {             flag[j]=true;             num/=j;         }     }     res=multmod(res,num,prime); } 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14402

 Ask a Question

 Download Related Notes/Documents