PROBLEM LINK:
Author: Alex Gu
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh
DIFFICULTY:
EasyMedium
PREREQUISITES:
Math
PROBLEM:
Given two sequences a and b and a recurrence to calculate a_i and b_i, we need to calculate a certain value c when a pair of corresponding terms of a and b are given.
EXPLANATION:
Subtask 1
For subtask 1, we can simply iterate from i to k (as the case may be) and use the recurrences to calculate a_k and b_k.
Now, there are two cases:

When i \leq k.
In this case, the given recurrence can be used directly. I.e.,
a_{n+1} = x(a_n + b_n)  xy(a_n  b_n)
b_{n+1} = x(a_n  b_n) + xy(a_n + b_n) 
When k < i.
In this case, the following recurrence can be derived and used.
a_{n1} = \frac{a_n + b_n  y(a_n  b_n)}{2x + 2xy^2}
b_{n1} = \frac{a_n  b_n + y(a_n + b_n)}{2x + 2xy^2}
The last step is to calculate 2^s. The calculation must be done in floating type to ensure that the answer doesn’t overflow. The inbuilt exponentiation function in most of the programming languages can do this job easily.
Subtask 2
Let us look at the original recurrences given to us, i.e.,
a_{n+1} = x(a_n + b_n)  xy(a_n  b_n)
b_{n+1} = x(a_n  b_n) + xy(a_n + b_n)
What do they tell us? Basically, we are given a_{n+1} and b_{n+1} in terms of a_n and b_n. Let us go a step further and try to calculate a_{n+2} and b_{n+2} in terms of a_n and b_n.
For doing this, we first note the following terms:
a_{n+1} + b_{n+1} = 2xa_n + 2xyb_n
a_{n+1}  b_{n+1} = 2xb_n  2xya_n
Now, we use our original recurrence to calculate a_{n+2} and b_{n+2}.
a_{n+2} = x(2xa_n + 2xyb_n)  xy(2xb_n  2xya_n) = a_n(2x^2 + 2x^2y^2)
b_{n+2} = x(2xb_n  2xya_n) + xy(2xa_n + 2xyb_n) = b_n(2x^2 + 2x^2y^2)
Since, x = \sqrt 2 and y = \sqrt 3, thus, (2x^2 + 2x^2y^2) = 16.
This leads us to a very important observation:
a_{n+2} = 16a_n
b_{n+2} = 16b_n
It tells us that if i and k are both even or both odd, then a_k + b_k = c(a_i + b_i), where c is a constant. When ki = 2, c = 2^4; when ki = 4, c = 2^8, and so on. Thus, c = 2^{2(ki)}.
When i and k are of different parities, i.e., one is even and the other is odd, we can first calculate a_{i+1} and b_{i+1} and then calculate a_k and b_k.
The last part is to calculate 2^s, which has already been explained in subtask 1.
COMPLEXITY:
All the operations take constant time except the use of exponentiation function. The inbuilt exponentiation function is implimented as \mathcal{O}(\log N) algorithm in all the programming languages.
Net complexity: \mathcal{O}(\log N).