Problem Link : Contest PracticeAuthor and Editorialist : Arun Prasad geek_geek Difficulty:Easy PREREQUISITES:Modular Arithmetic,Combinatorics,Repeated Squaring PROBLEMGiven n items , find number of ways to choose k different items. QUICK EXPLANATIONYou have to find the value of nCk it will give you number of ways of choosing k items from n items print nCk % mod (mod = 1000000007) EXPLANATIONnck = (n!)/((nk)! * k!) now you cannot store n! in an array as it can be very big instead you can store n!%mod in an array since mod is a prime number you have to use fermat's theorem to calculate the value of modular inverse of ((k!)%mod) and ((nk)!%mod) store the value of n!%mod in an array , and calculate inverse factorial for each n by using the formula inv_factorial(n) = exp(n,mod2,mod) (use repeated squaring for faster answers) store all in an array if n is greater tha k : nCk = (fact(n)inv_fact(nk)inv_fact(k))%mod if n is lesser than k You cannot choose k items from n if k is greater than n hence answer is 0 Solutions : Author's Solution
This question is marked "community wiki".
asked 29 Jun '15, 18:40
