### Problem Link:

**Author:** Vaibhav Srivastava

**Tester:** Shivam Garg and Vaibhav Srivastava

**Editorialist:** Saurabh Kumar

### Difficulty:

Easy

### Prerequisites:

Permutation, mod-inverse

### Problem:

We are given number of people in 3 different groups (let’s say A, B and D). We have to output how many different ways are there to form a team among the groups in a way such that:-

i. There is at least 1 member from each group in a team.

ii. Number of member from group A has to be one more than the number of members from group B.

### Quick Explanation:

The number of ways can be calculated by the formula:-

\sum_{2}^{A}(_{i}^{A}\textrm{C}*\sum_{1}^{min(B,i-1)}(_{j}^{B}\textrm{C})*(2^{D} - 1))

where, _{i}^{A}\textrm{C} = \frac{A!}{(i)!(A-i)!}.

### Explanation:

The number of ways of selecting i people from a group of A people is _{i}^{A}\textrm{C} which equals \frac{A!}{(i)!(A-i)!}. Now as given in the question if we select i people from group A then we can select 1 to (i-1) number of people from group B which becomes \sum_{1}^{i-1}(_{j}^{B}\textrm{C}). B can also be less than i-1 therefore the summation changes to \sum_{1}^{min(i-1, B)}(_{j}^{B}\textrm{C}). And the number of ways of selecting 1 or more people from a group of D peoples is (2^{D} - 1).

Combining all these 3 equations we get the formula:-

\sum_{2}^{A}(_{i}^{A}\textrm{C}*\sum_{1}^{min(i-1, B)}(_{j}^{B}\textrm{C})*(2^{D} - 1))

So, we use two nested loops i and j. i from 2 to A and j from 1 to minimum of (i-1, B) and we can count the ways using the formula and keep adding to the final answer. One thing to note is that we can pre-compute the nCr values before the test cases and this would help in reducing the time complexity and getting accepted.

**Time Complexity** becomes O(A*B) which equals O(10^6).

Author’s solution can be found here.