DSERIES – Editorial

easy
editorial
locmay18
math

#1

PROBLEM LINK:

Practice

Contest

Author: Abhijeet Jha

Tester: Aswin Ashok

Editorialist: Aswin Ashok

DIFFICULTY:

EASY

PREREQUISITES:

Math, Modular Arithmetic

PROBLEM:

Find \sum_{i=1}^{n}\prod_{k=1}^{t}(i+k). Print the sum \mod 10^9+7.

QUICK EXPLANATION:

The final answer is t!*(^{n+t+1}C_{t+1}-1)

EXPLANATION:

Let us take the given example and try to reduce it to a general formula.

In the Given Sample Case n=3 t=2.

Therefore sum = 2*3 + 3*4 + 4*5

Notice that:

1*2=\frac{2!}{0!}

2*3=\frac{3!}{1!}

3*4=\frac{4!}{2!}

4*5=\frac{5!}{3!}

So each term is of the form \frac{x!}{(x-t)!}

If we multiply and divide by t! it becomes t!*\frac{x!}{(x-t)!t!}

Which is nothing but t!* ^xC_t

Therefore sum = t!*\sum_{x=t+1}^{n+t}\ ^xC_t

But we know \sum_{x=t}^{N}\ ^xC_t = ^{N+1}C_{t+1}

Therefore \sum_{x=t+1}^{n+t}\ ^xC_k =^{n+t+1}C_{t+1} - 1

So final expression comes out to be t!* ^{n+t+1}C_{t+1} -t!

But since n is so large we can not calculate it directly, we have to Simplify the above expression.

On Simplifying we get \frac{\prod_{i=1}^{t+1} (n+i)}{t+1}-t!

TIME COMPLEXITY

For each test case the final simplified expression can be evaluated in O(t) and there are Q test cases so overall complexity is O(Q*t)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.


#2

Hello,I am a school student ,
the maths requried for LOC is of a bit high level.
I would be grateful if u all can suggest tutorials or books from which I can study.:slight_smile: