Problem Link : Contest Practice
Author and Editorialist : Arun Prasad geek_geek
Difficulty:
Easy
PREREQUISITES:
Modular Arithmetic,Combinatorics,Repeated Squaring
PROBLEM
Given n items , find number of ways to choose k different items.
QUICK EXPLANATION
You 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)
EXPLANATION
nck = (n!)/((n-k)! * 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 ((n-k)!%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,mod-2,mod) (use repeated squaring for faster answers)
store all in an array
if n is greater tha k :
nCk = (fact(n)*inv_fact(n-k)*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