### PROBLEM LINK:

**Author:** ???

**Tester:** Kevin Atienza, Jingbo Shang

**Editorialist:** Kevin Atienza

### PREREQUISITES:

Modulo, recurrences, pattern matching

### PROBLEM:

A function f on integers is defined:

- f(1) = A, f(2) = B.
- For all integers x \ge 2, f(x) = f(x-1) + f(x+1).

Find f(N) \bmod (10^9 + 7).

### QUICK EXPLANATION:

f is periodic with period 6, so f(N) is equal to f(N \bmod 6). (Just define f(0) = A-B.)

### EXPLANATION:

At first glance, this problem seems to require standard techniques in solving general linear recurrences. While those techniques will work, they are quite overkill for this problem. Simple pattern spotting will do (This solution is much faster to code and very easy to find, so you’ll probably be able to get AC earlier with it. The few minutes you save is sometimes significant.)

The key is to simply compute the first few terms. As an example, let’s say A = 11 and B = 9. Since f(x+1) = f(x) - f(x-1) (a rearrangement of the above), we have:

- f(\,\,3) = f(\,\,2) - f(\,\,1) = -2
- f(\,\,4) = f(\,\,3) - f(\,\,2) = -11
- f(\,\,5) = f(\,\,4) - f(\,\,3) = -9
- f(\,\,6) = f(\,\,5) - f(\,\,4) = 2
- f(\,\,7) = f(\,\,6) - f(\,\,5) = 11
- f(\,\,8) = f(\,\,7) - f(\,\,6) = 9
- f(\,\,9) = f(\,\,8) - f(\,\,7) = -2
- f(10) = f(\,\,9) - f(\,\,8) = -11
- f(11) = f(10) - f(\,\,9) = -9
- f(12) = f(11) - f(10) = 2
- …

At this point, you might notice that the sequence repeats every 6 terms. Once you notice this, you might think to try to prove it rigorously before coding it. Though proving it is simple, you don’t have to do it; you just pray to the god of pattern matching and hope that this pattern will go on forever (or you trust your instinct). Though this doesn’t always work, with experience and intuition, you’ll eventually learn which of the unproven statements / observations you make may actually be true.

*Note:* Don’t forget to ensure that f(N) \bmod (10^9 + 7) is positive! Also, f(N) can be < -(10^9 + 7), so adding (10^9 + 7) just once isn’t enough to make f(N) positive.

# Proving it

But as just mentioned, proving it is simple. Let’s first generalize the observation above, by actually using variables A and B:

- f(3) = f(2) - f(1) = B - A
- f(4) = f(3) - f(2) = -A
- f(5) = f(4) - f(3) = -B
- f(6) = f(5) - f(4) = A - B
- f(7) = f(6) - f(5) = A
- f(8) = f(7) - f(6) = B
- f(9) = f(8) - f(7) = B - A
- f(10) = f(9) - f(8) = -A
- f(11) = f(10) - f(9) = -B
- f(12) = f(11) - f(10) = A - B
- …

Let’s now prove that this pattern will go on forever:

*Claim:* For n \ge 1, f(n) = f(n+6).

*Proof:*

Clearly, this is true for n = 1 and n = 2 (because f(1) = f(7) = A and f(2) = f(8) = B). Now, assume n > 2. Assume by induction that it is true for all 1 \le n' < n. So it must be true for n-2 and n-1. Then:

This proves the claim.

*End of proof*

The general idea is that because each term f(n) depends only on the previous two terms (f(n-2), f(n-1)), once two consecutive terms repeat, the whole function will repeat forever. In our case, since (A,B) repeated, we’re sure that the following sequence will just repeat previous terms after that.

This also works even if f(n) is not a linear recurrence! If f(n) = g(f(n-2), f(n-1)) for some function g, then regardless of the nature of g, as long as you find a repeat of the pair (f(n-2),f(n-1)), the function f will repeat after that point. This also works if f was a recurrence that depended on more than two previous terms, say k \ge 2, though this time you’ll need to keep track of a k-tuple of values instead of a pair.

# More properties

Let’s analyze f more deeply. Using generating functions, we can actually find a neat formula for f. (though it doesn’t necessarily yield any algorithmic improvements, it is interesting nonetheless.) It will also explain why every three terms *almost* repeats, except that you have to flip the sign first. To make things cleaner, in the following we’ll write f_n as a synonym of f(n). We’ll also define f(0) = A - B, so the recurrence still holds.

Let F(x) = f_0 + f_1x + f_2x^2 + f_3x^3 + \ldots. Then:

Now, consider F(x) - xF(x) + x^2F(x), by adding like terms together. Since f_n = f_{n-1} - f_{n-2}, almost all terms will cancel out. The only nonzero terms are the constant and linear term. Thus, we have:

Now, let’s try to factorize 1 - x + x^2. It has two roots: \dfrac{1 \pm \sqrt{3}i}{2}. Let us use the symbol \psi and \bar{\psi} for \dfrac{1 + \sqrt{3}i}{2} and \dfrac{1 - \sqrt{3}i}{2}, respectively (\bar{x} denotes *complex conjugation*). Thus, 1 - x + x^2 must be equal to (x - \psi)(x - \bar{\psi}). But since \psi\bar{\psi} = 1, we get:

Note that \psi and \bar{\psi} are both *primitive 6 th roots of unity*, so \psi^6 = \bar{\psi}^6 = 1. (verify)

Back to F(x), we get:

At this point, let’s use the method of partial fractions, to obtain

where C and D are constants that we don’t know yet. This form is very useful to us because of the equality:

which means that the coefficient of x^n in F(x) is just C\psi^n + D\bar{\psi}^n, giving us a formula for f(n). Right away, this tells us that f(n) is periodic with period 6, because \psi and \bar{\psi} are both primitive 6 th roots of unity. It also explains why f(n) = -f(n+3): It’s because \psi^3 = \bar{\psi}^3 = -1.

To compute C and D, simply add the two fractions together and equate coefficients:

Thus, we get C + D = A - B and C\bar{\psi} + D\psi = A. By solving this system, we get

This gives us the following formula for f(n):

In general, for any periodic sequence g(n) with period k, g always has some formula that looks like:

where \omega_k is a primitive k th root of unity (so \{1, \omega_k, \omega_k^2, \ldots, \omega_k^{k-1}\} is the complete set of k th roots of unity).

### Time Complexity:

O(1)

### AUTHOR’S AND TESTER’S SOLUTIONS:

[setter][333]

[tester][444]

[editorialist][555]

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.

[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.

[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.