You are not logged in. Please login at www.codechef.com to post your questions!

×

# DSERIES – Editorial

Author: Abhijeet Jha
Tester: Aswin Ashok
Editorialist: Aswin Ashok

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.

asked 02 Jun '18, 20:19

143
accept rate: 0%

19.8k350498541

 0 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.:) answered 01 Jul '18, 18:41 104●7 accept rate: 2%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,764
×877
×22

question asked: 02 Jun '18, 20:19

question was seen: 596 times

last updated: 01 Jul '18, 18:41