NOWAYS Editorial

easy
editorial
hoco2015
noways
numberofways

#1

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

Solutions : Author’s Solution