DBFB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

Author: anuj_2106

Tester: Suchan Park

Editorialist: Suchan Park

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

Tester’s solution can be found here.