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).
$$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
