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


DBFB - Editorial




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.




Almost none, good to know properties of Fibonacci numbers


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]


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.


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

tncks0121's gravatar image

accept rate: 0%

edited 10 Aug, 19:34

admin's gravatar image

0★admin ♦♦
19.6k349497539 what have i done wrong in this??


answered 23 May, 11:31

veda_19's gravatar image

accept rate: 0%

edited 23 May, 11:31

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 19 May, 18:15

question was seen: 937 times

last updated: 10 Aug, 19:34