PROBLEM LINK:Author: Vasia Antoniuk DIFFICULTY:Easy PREREQUISITES:Combinatorics PROBLEM:Given an array A of N integers, a position x, and a number M, find the value of $A_x$ after performing the following operation M times:
As the answer could be large, the answer should be given modulo $1\,000\,000\,007$. EXPLANATION:Subtask1In the first subtask, we have $x \leq 2$. So we only have 2 cases:
Subtask 2The second subtask guarantees that $N \times M \leq 10^6$. This means that we can just perform the given algorithm M times. This approach takes $O(N\times M)$ time, which is ok with these constraints. Subtask 3The number $N$ is irrelevant if larger than $x$ because $A_x$ is only affected by indices smaller than $x$. Hence, I will consider $N=x$ for the rest of the editorial, i.e., we will want to know the value of $A_N$. When we are given a set of operations to be performed, a good starting point is to see what happens after a few iterations. Suppose we have $N = 5$, and the initial values are $A_1 = a$, $A_2 = b$, $A_3 = c$, $A_4 = d$, and $A_5 = e$. You may recognise that the factors associated with each initial value are binomial coefficients. In each step, we are summing the values of a column in the Pascal Triangle. In the above example, $M= 5$, so we are interested in summing the first 5 lines in each column. For example, the value associated with a in the final $A_5$ is the result of $\binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3} + \binom{7}{3}$. It can be shown (see here) that $\sum_{m=0}^n{\binom{m}{k}} = \binom{n+1}{k+1}$. In fact, $\sum_{m=0}^7{\binom{m}{3}} = \binom{8}{4} = 70$. So, we now have a formula to get the coefficient of each initial value, in order to get the final $A_N$. In the above example, we have $A_5 = \binom{M+3}{4} a + \binom{M+2}{3} b + \binom{M+1}{2} c + \binom{M}{1} d + \binom{M1}{0} e = \\ \binom{8}{4} a + \binom{7}{3} b + \binom{6}{2} c + \binom{5}{1} d + \binom{4}{0} e = \\ 70a + 35b + 15c + 5d + e$ The binomial coefficient can be calculated as $\binom{n}{k} = \frac{n!}{k! (nk)!}$. M is up to $10^{18}$ so it is too big to calculate the factorial directly. However, we can take advantage of the formula we are calculating. $\binom{M+3}{4} = \frac{(M+3)!}{4! (M+34)!} = \frac{(M+3)!}{4! (M1)!} = \frac{M * (M+1) * (M+2) * (M+3)}{4!}$ $\binom{M+2}{3} = \frac{M * (M+1) * (M+2)}{3!}$ $\binom{M+1}{2} = \frac{M * (M+1)}{2!}$ $\binom{M}{1} = \frac{M}{1!}$ $\binom{M1}{0} = 1$ As you can see, we can calculate each factor iteratively using the previous value. In order to divide by each factorial, we need to use the Modular Multiplicative Inverse, which can be computed in $O(\log{N})$. So, the time complexity of this approach is $O(N \log{N})$. Sample Solutionsasked 13 Feb '16, 00:37

solution idea for 3 easy problems. https://shadekcse.wordpress.com/2016/02/15/codecheffeb16challenge/ answered 15 Feb '16, 16:59

The coefficients in the solution are actually the m'th diagonal of the pascal's triangle.. For easier and clear solution, you might want to see My solution: answered 15 Feb '16, 18:13

Can make that O(n) by calculating coefficients Instantly. https://www.codechef.com/viewsolution/9308756 answered 15 Feb '16, 15:15
1
The extra O(log N) factor comes from calculating the modular multiplicative inverse. Your approach is O(N log N).
(15 Feb '16, 16:08)

Can someone help me in optimizing the code? It gives TLE for subtask 3's test cases. https://www.codechef.com/viewsolution/9425309 answered 15 Feb '16, 15:26

can someone explain about the line For example, the value associated with a in the final A5 is the result of c(3,3)+c(4,3)+c(5,3)+c(6,3)+c(7,3);? how did you obtain this?
link
This answer is marked "community wiki".
answered 20 Feb '16, 16:08

Can someone please point out the logical error in my code . this give WA for subtask #2 but passes all of my test cases could be a great help for me https://www.codechef.com/viewsolution/9455251 answered 20 Feb '16, 20:27

Can anyone tell me what's wrong with my submission? I keep getting WA on 2 tests of the last sub task. I figured out the coefficient series as Thank You answered 13 Jul '18, 10:27

For an easy implementation, you may refer to My solution. answered 15 Feb '16, 16:25
