 # SCC0105 - Editorial

Contest

Practice

### PROBLEM NAME: Tricks of Tom

Author: Learners Club

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=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