SCC0105 - Editorial

PROBLEM LINK:

Contest

Practice

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:

  1. 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})

  2. 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 )

  3. Hence we have K-1 locations to choose from S-1 location which can be computed as (s-1)C(k-1)

  4. 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 :

RELATED PROBLEMS:

Stars and Bars: Combinatrics