PROBLEM LINK:Author: Abhijeet Jha 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!}$ If we multiply and divide by $t!$ it becomes $t!*\frac{x!}{(xt)!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 COMPLEXITYFor 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. asked 02 Jun '18, 20:19

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
