ans = factorial(n) /factorial(r1) factorial(r2)…factorial(rk) where r1+r2+…+rk= n how to calculate this vale when n is large?
I want the ans mod 1000000007 value any suggestions will be appreciated
ans = factorial(n) /factorial(r1) factorial(r2)…factorial(rk) where r1+r2+…+rk= n how to calculate this vale when n is large?
I want the ans mod 1000000007 value any suggestions will be appreciated
Let us consider the general case for any such problem.
ans= numerator/denominator.
Let P be any prime number
So you have to calculate ans%P, given that you have numerator and denominator.
For such cases the answer comes out to be:
ans= (numerator%P * power(denominator%P,P-2))%P.
Now for your case you can easily calculate the numerator and denominator by pre-storing the factorial values, so all that is left is to calculate (numerator/denominator)%P.
Note: To emphasize once again, this technique can be used only when P is a prime number.
What I see is you have n as large than you could have a precomputation of combinations using Pascal triangle and modulus this with 1000000007 as the value may become large and than just multiply the combinations like ncr1* (n-r1)cr2*…*(n-(rk-2)c(rk-1)(mod) ans…
You could consider this question similar to it http://www.spoj.com/problems/GOODB/
ans= (numerator%P * power(denominator%P,P-2))%P.
can u xplain how dis equation comes… will b realy grateful