DBFB - Editorial

general
1

PROBLEM LINK:

[Practice][https://www.codechef.com/problems/DBFB]
[Contest][https://www.codechef.com/MAY18A/problems/DBFB]

Author: [anuj_2106][https://www.codechef.com/users/anuj_2106]
Tester: [tncks0121][https://www.codechef.com/users/tncks0121]
Editorialist: [tncks0121][https://www.codechef.com/users/tncks0121]

DIFFICULTY:

Easy

PREREQUISITES:

None, Fibonacci Sequence

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:

Express this code in terms of mathematical notations,

EXPLANATION:

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found [here][333].
Tester’s solution can be found [here][444].