矩阵乘法
定义矩阵乘法的运算规则如下
\[A\left[m\right]\left[n\right] * B\left[n\right]\left[p\right] = C\left[m\right]\left[p\right] \]其中 \(C\left[i\right]\left[j\right]\) 等于 \(A\) 的第 \(i\) 行乘 \(B\) 的第 \(j\) 列，举例如下
\[\begin{bmatrix} 5&6\\7&8 \end{bmatrix} * \begin{bmatrix} 1&2&3\\4&5&6 \end{bmatrix} = \begin{bmatrix} 5*1+6*4&5*2+6*5&5*3+6*6 \\ 7*1+8*4&7*2+8*5&7*3+8*6 \end{bmatrix} \]矩阵乘法的性质
- 满足分配率和结合律，不满足交换率
- \(A\) 的列数必须等于 \(B\) 的行数
用斐波那契数列引入矩阵快速幂
已知斐波那契数列
\[f_n=f_{n-1}+f_{n-2} \]其中
\[\begin{cases} f_0=0\\f_1=1 \end{cases} \]则有
\[\begin{bmatrix} f_{n+1}&f_n \end{bmatrix} = \begin{bmatrix} f_n&f_{n-1} \end{bmatrix} * \begin{bmatrix} 1&1\\1&0 \end{bmatrix} = {\begin{bmatrix} f_{n-1}&f_{n-2} \end{bmatrix} * \begin{bmatrix} 1&1\\1&0 \end{bmatrix}}^2 = {\begin{bmatrix} f_1&f_0 \end{bmatrix} * \begin{bmatrix} 1&1\\1&0 \end{bmatrix}}^n \]求解广义斐波那契数列
广义斐波那契数列数列的公式
\[f_n=a*f_{n-1}+b*f_{n-2} \]则有
\[\begin{bmatrix} f_{n+1}&f_n \end{bmatrix} = \begin{bmatrix} f_n&f_{n-1} \end{bmatrix} * \begin{bmatrix} a&1\\b&0 \end{bmatrix} = {\begin{bmatrix} f_1&f_0 \end{bmatrix} * \begin{bmatrix} a&1\\b&0 \end{bmatrix}}^n \]求解系数含有0的递推函数
已知公式
\[f_n=3*f_{n-1}+5*f_{n-3}+9*f_{n-4} \]则有
\[\begin{bmatrix} f_{n+3}&f_{n+2}&f_{n+1}&f_n \end{bmatrix} = \begin{bmatrix} f_3&f_2&f_1&f_0 \end{bmatrix} * {\begin{bmatrix} 3&1&0&0\\0&0&1&0\\5&0&0&1\\9&0&0&0 \end{bmatrix}}^n \]将系数为0的项对应的矩阵中的位置置0
求解一般递推函数
已知公式
\[f_n=a*f_{n-1}+b*f_{n-3}+c \]则有
\[\begin{bmatrix} f_{n+2}&f_{n+1}&f_n&c \end{bmatrix} = \begin{bmatrix} f_2&f_1&f_0&c \end{bmatrix} * {\begin{bmatrix} a&1&0&0\\0&0&1&0\\b&0&0&1\\1&0&0&0 \end{bmatrix}}^n \]将常数项加入待求的矩阵中一并运算，并将计算矩阵相对应的位置置1以确保常数项的值不变
求解有下标的递推函数
已知公式
\[f_n=f_{n-1}+2*f_{n-2}+n^3 \]这里需要用到一个知识：立方的展开
\[n^3=(n-1)^3+3(n-1)^2+3(n-1)+1 \]事实上，矩阵乘法求递归问题也可以用纵向的矩阵表示，如下
\[\begin{bmatrix} f_n\\f_{n-1}\\n^3\\n_2\\n\\1 \end{bmatrix} = \begin{bmatrix} f_2\\f_1\\8\\4\\2\\1 \end{bmatrix} * {\begin{bmatrix} 1&2&1&3&3&1 \\ 1&0&0&0&0&0 \\ 0&0&1&3&3&1 \\ 0&0&0&1&2&1 \\ 0&0&0&0&1&1 \\ 0&0&0&0&0&1 \end{bmatrix}}^{n-2} \] 标签：begin,right,end,矩阵,bmatrix,快速,left From： https://www.cnblogs.com/xj22yangyichen/p/17364301.html