cpcesar's blog

By cpcesar, history, 5 weeks ago, In English,

I'm solving problem K of this contest:
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$$$
$$$f(2) = 6$$$
$$$f(n) = 2^{n-1}+2f(n-1)+4f(n-2) \qquad \forall n > 2$$$

$$$g(3) = 4$$$
$$$g(n) = 4f(n-2)+2g(n-1) \qquad \forall n > 3$$$

The result for input $$$n$$$ is $$$4f(n) + 2g(n)$$$, 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?

  • Vote: I like it
  • -1
  • Vote: I do not like it

5 weeks ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

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:

$$$ \begin{bmatrix} h_1(k+1)\\ r(k+1)\\ h_0(k+1) \end{bmatrix} = \begin{bmatrix} 2 & 0 & 4\\ 0 & 2 & 4\\ 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_1(k)\\ r(k)\\ h_0(k) \end{bmatrix} $$$

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)$$$.

  • »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it