PROBLEM LINK:
PROBLEM NAME: Tricks of Tom
Author: Learners Club
DIFFICULTY:
MEDIUM
PREREQUISITES:
Permutations, Inverse Modulo, nCr
PROBLEM:
In Short we were required to find the count of all possible solution such that by picking any K positive numbers we would be able
to form the sum S.
EXPLANATION:
The problem was a basic combinatorial problem.
You have to make a sum S by picking any K positive
integers ( repetition allowed and order of picking is important).
This problem can be visualized as suppose:
-
You have S one unit blocks lying in a row then their sum
will be S ( in case S=7 can be represented as {1,1,1,1,1,1,1}) -
And now if make k partition of this set the
sum remains S ( if k=2 the sets possible are { 1,1,1 | 1,1,1,1} ) So our problem reduces to breaking this
set S into k sets. ( for S=7 we have 1 __ 1__ 1__ 1__ 1__ 1__1 => 6 (7-1) places to intoduce this Cut
to make new segment. 1 cut produces 2 segments similarly K-1 cuts produce K sets ) -
Hence we have K-1 locations to choose from S-1 location which can be computed as (s-1)C(k-1)
-
In case K>S the answer will be -1.
Computation of nCr
Now all that was required was to precompute the nCr unto the given constraint in O(n) using modular
an inverse modular arithmetic.
For that we compute the fact[1…n] array in one pass
in which at index i factorial(i)%mod is stored :
fact[0]=1; // 0! = 1
mod=10^9+7
for(int i=1;i<n;i++)
{
fact[i]=(i*fact[i-1])%mod;
}
Now we have fact[n]%mod.
**nCr => [n!/((n-r)! * r!)] % mod
=> [ (n!)%mod * (((n-r)!)^-1)%mod * ((r!)^-1)%mod ] %mod
(a^-1)%mod => inv_modulo(a%mod) => power( a , mod-2 ) //Power function has complexity
O(log(n))**
Also another point to note is that N!= N*(N-1)!
Hence (N!)^-1 = [N*(N-1)!]^-1
So we can deduce that:
inv_modulo( (N-1)! ) = [ N* inv_modulo( N!) ] %mod
now we need to compute in O(n) inv_modulo of fact[1…n] and store the result in invfact[1…n] which
at index I stores (fact[i]^-1)%mod
invfact[n]=pow(fact[n],mod-2);
// compute invfact%mod
for(int i=n-1;i>=0;i–)
{
invfact[i]=((i+1)*invfact[i+1])%mod;
}
nCr = [ fact[n]*invfact[n-r]*invfact[r] ]% mod
Hence the overall complexity O(n).
Check out the following link :