# PROBLEM LINK:

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

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,

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:

Use the properties of \Sigma to simplify the summation:

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.