PROBLEM LINK:
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.
