可以用来加速 dp，解决值域大的问题。
$ \text{Examples:} $
和某个入门题很像，但值域扩大到了 $ [1, 2^{63}) $ ，当然不能暴力求解，考虑把 $ f_{n} $ 和 $ f_{n - 1} $ 当成向量写在一起：\(\begin{bmatrix} f_{n} \\ f_{n - 1} \end{bmatrix}\)，然后找出使下列等式成立的矩阵 $ \textbf{A} $：
\[\begin{bmatrix} f_{n} \\ f_{n - 1} \end{bmatrix} = \textbf{A}\begin{bmatrix} f_{n - 1} \\ f_{n - 2} \end{bmatrix} \]容易得出：$ \textbf{A}$ \(= \begin{bmatrix} 1 & 1 \\\ 1 & 0\end{bmatrix}\)。那么，乘上 $ n - 2 $ 次 $ \textbf{A} $ 后就是这样的：
\[\begin{bmatrix} f_{n} \\ f_{n - 1} \end{bmatrix} = \textbf{A}^{n - 2}\begin{bmatrix} f_{2} \\ f_{1} \end{bmatrix} \]如何计算 $ \textbf{A}^{n - 2} $呢？考虑快速幂：开一个结构体Matrix并重载*运算符，写一个矩阵的快速幂。
与上一题相同，类比得到：
\[\begin{bmatrix} a_{n} \\ a_{n - 1} \end{bmatrix} = \textbf{A}^{n - 2}\begin{bmatrix} a_{2} \\ a_{1} \end{bmatrix} \]\[\textbf{A} = \begin{bmatrix} p & q \\ 1 & 0 \end{bmatrix} \]这题的递推式有些奇怪，但不影响我们推，所以考虑开一个四维向量，如下：
\[\begin{bmatrix} f_{x} \\ f_{x - 1} \\ f_{x - 2} \\ f_{x - 3} \end{bmatrix} = \textbf{A}^{x - 4}\begin{bmatrix} f_4 \\ f_3 \\ f_2 \\ f_1 \end{bmatrix} \]再将 $ f_x $ 代换成 $ f_{x - 1} + f_{x - 3} $，解出：
\[\textbf{A} = \begin{bmatrix} 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \] 标签：begin,end,矩阵,笔记,textbf,斐波,bmatrix,乘法 From： https://www.cnblogs.com/CusetNekomusume/p/18117817