PROBLEM LINK:Author: anuj_2106 Tester: Suchan Park Editorialist: Suchan Park I wasn't aware that the actual editorialist wrote an editorial here, but anyway I decided to upload my work to avoid confusion. DIFFICULTY:Easy PREREQUISITES:Almost none, good to know properties of Fibonacci numbers PROBLEM:Given two sequences $A$ and $B$ with size $M$, and an integer $N$, compute the
QUICK EXPLANATION:Analyze what the innermost loop is doing, and then it is easy to see that EXPLANATION:Let's first analyze the innermost part of the loop. This part adds
As you can see from the name and the form of the recurrence, it is very similar to the wellknown Fibonacci sequence. The only difference is that the first two terms are $A[i]$ and $B[j]$, not 0 and 1 (or 1 and 1) as usual. Since the recurrence only sums up the last two elements, we can see that for each $k$, we can express $fib[k]$ as $$fib[k] = C_k \cdot A[i] + D_k \cdot B[j]$$ for some fixed constants $C_k$ and $D_k$. Let's find what $C_k$ and $D_k$ are. From the definition of the sequence,
Now, using this recurrence, we are able to compute the values of $C_{N}$ and $D_{N}$ (using dynamic programming). Also, you can notice that $C_{k}$ and $D_{k}$ are successive elements of the fibonacci sequence (write down $C_{k}$ and $D_{k}$, and you will see!) In conclusion, $$fib[n] = C_{N} \cdot A[i] + D_{N} \cdot B[j]$$ The outer loop just iterates all $1 \le i, j \le M$ and sums up all $$\sum_{i=1}^{M} \sum_{j=1}^{M} \{ C_{N} \cdot A[i] + D_{n} \cdot B[j]\}$$ Use the properties of $\Sigma$ to simplify the summation: $$\begin{aligned} \sum_{i=1}^{M} \sum_{j=1}^{M} \{ C_{N} \cdot A[i] + D_{N} \cdot B[j]\} &= \sum_{i=1}^{M}\sum_{j=1}^{M} C_N \cdot A[i] + \sum_{i=1}^{M}\sum_{j=1}^{M} D_{N} \cdot B[j] \\ & = M \cdot C_{N} \cdot \sum_{i=1}^{N} A[i] + M \cdot D_{N} \cdot \sum_{j=1}^{M} B[j] \end{aligned}$$ Now, it is easy to calculate each part  we can construct the answer using the sums of array $A$ and $B$, and the coefficients $C_{N}$ and $D_{N}$. Note that we need to keep the answer value $10^9 + 7$ during the whole computation, to avoid overflow. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here.
This question is marked "community wiki".
asked 19 May, 18:15

https://www.codechef.com/viewsolution/18503035 what have i done wrong in this?? answered 23 May, 11:31
