Hi,
I'm solving problem K of this contest:
http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf
and I know it can be solved with fast matrix exponentiation.
I got to the step where I have the following two recurrences:
$$$f(1) = 1$$$
Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
Unable to parse markup [type=CF_MATHJAX]
The result for input $$$n$$$ is
Unable to parse markup [type=CF_MATHJAX]
, when n > 2.But I have no idea how to find matrices to compute such recurrences.
Could someone please suggest me a good reference from where I can learn to find the correct matrices when solving matrix exponentiation problems?
UPD. Maybe you already know, but while $$$n \le 10^9$$$ you can solve it in $$$O(n)$$$.
You need to introduce new function $$$h(n)$$$ in form $$$h(n)=f(n)-C \cdot 2^n$$$ and find such $$$C$$$ that after substitution into recurrence for $$$f(n)$$$ the term with $$$2^n$$$ will be equal to zero. After it you will have next recurrences:
$$$h(n)=2\cdot h(n-1) + 4 \cdot h(n-2)$$$ and $$$g(n)=4 \cdot \left(h(n-2)+C \cdot 2^{n-2}\right) + 2 \cdot g(n-1)$$$
After it you can apply this trick for recurrence for $$$g(n)$$$ too: introduce new function $$$r(n)$$$ that $$$r(n)=g(n)-C_1 \cdot 2^n$$$ and after finding $$$C_1$$$ you will have next recurrences:
$$$h(n)=2 \cdot h(n-1)+4 \cdot h(n-2)$$$ and $$$r(n)=4 \cdot h(n-2)+2 \cdot r(n-1)$$$. Now you can solve it with matrix exponentiation:
UPD 2. A much easier way: introduce third function $$$h(n) = 2^{n-1}$$$. So, you will have linear recurrences for $$$h(n)$$$, $$$f(n)$$$ and $$$g(n)$$$.
Thanks for your explanation. I have found $$$C = -\frac{1}{2}$$$, but I got stuck on the step where I introduce $$$r(n) = g(n) - C_1 \cdot 2^{n}$$$ and try to find $$$C_1$$$.
$$$r(n) = g(n) - C_1 \cdot 2^{n} \implies g(n) = r(n) + C_1 \cdot 2^{n}$$$
1) $$$g(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot g(n-1)$$$
2) $$$r(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot [r(n-1) + C_1 \cdot 2^{n-1}] - C_1 \cdot 2^{n}$$$
3) $$$r(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot r(n-1) + C_1 \cdot 2^{n} - C_1 \cdot 2^{n}$$$
4) $$$r(n) = -2^{n-1} + 4 \cdot h(n-2) + 2 \cdot r(n-1)$$$
$$$C_1$$$ got cancelled in line 3 so I cant find it. Another thing I would like to question if you don't mind: This trick seems to be applied to get a linear recurrence from another one that is not linear. Can matrix exponentiation be applied only to linear recurrences?
Looks like it's not working with $$$C_1$$$. The only one way is introduce new function $$$h(n) = 2^{n}$$$, $$$h(n)=2h(n-1)$$$, $$$h(1)=2$$$ and add it to system. You can read about it in the link from another comment below.
This trick can help only in transforming linear reccurence into homogeneous linear recurrence.
Matrix Exponentiation