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

×

DSERIES – Editorial

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.

asked 02 Jun '18, 20:19

aswinashok44's gravatar image

5★aswinashok44
143
accept rate: 0%

edited 07 Jun '18, 16:33

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 01 Jul '18, 18:41

krishyadav007's gravatar image

2★krishyadav007
1047
accept rate: 2%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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