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

×

# DBFB - Editorial

Practice

Contest

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.

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 result of this code modulo $10^9 + 7$.

result := 0 for i := 1 to M for j := 1 to M array fib[1..max(2, N)] fib[1] := A[i] fib[2] := B[j] for k := 3 to N fib[k] := fib[k-1] + fib[k-2] result := result + fib[N]

# QUICK EXPLANATION:

Analyze what the innermost loop is doing, and then it is easy to see that fib[N] is a linear combination of $A[i]$ and $B[j]$, and the coefficients of them form a fibonacci sequence. Then, write down the whole summation, and simplify it using the properties of summation.

# EXPLANATION:

Let's first analyze the innermost part of the loop. This part adds fib[N] to result, where fib is a sequence defined by the following:

• $fib[1] = A[i]$
• $fib[2] = B[j]$
• For $k \ge 3$, $fib[k] = fib[k-1] + fib[k-2]$

As you can see from the name and the form of the recurrence, it is very similar to the well-known 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,

• $fib[1] = A[i] = 1 \cdot A[i] + 0 \cdot B[j] \rightarrow C_1 = 1, D_1 = 0$
• $fib[2] = B[j] = 0 \cdot A[i] + 1 \cdot B[j] \rightarrow C_2 = 0, D_2 = 1$
• For $k \ge 3$,
• $fib[k] = fib[k-1] + fib[k-2]$
• $= C_{k-1} \cdot A[i] + D_{k-1} \cdot B[j] + C_{k-2} \cdot A[i] + D_{k-2} \cdot B[j]$
• $= (C_{k-1} + C_{k-2}) \cdot A[i] + (D_{k-1} + D_{k-2}) \cdot B[j]$
• $\rightarrow C_{k} = C_{k-1} + C_{k-2}, D_{k} = D_{k-1} + D_{k-2}$

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 fib[N]. Therefore, we can write the value of result as:

$$\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

137
accept rate: 0%

19.3k348495534

 0 https://www.codechef.com/viewsolution/18503035 what have i done wrong in this?? answered 23 May, 11:31 2★veda_19 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,005
×3,393
×105
×3

question asked: 19 May, 18:15

question was seen: 871 times

last updated: 10 Aug, 19:34