8
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前言
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
好久没有发帖子了，今天写个创作计划吧。
各位大佬嘴下留情，不喜轻喷，欢迎提建议！
本文将用通俗易懂的方法讲懂矩阵快速幂
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
铺垫
（若你已经知道且学会快速幂和矩阵乘法，可以直接跳到正文部分）
一、快速幂
先来复习一下快速幂。
以上是一个简单的快速幂模板。（如果到这里你没有看懂，请重学快速幂）
二、矩阵
矩阵，相当于 c++ 中的二维数组，是一个整齐排列的“数字表格”，举个例子：
[1,14,51,4]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix} 1,14,51,4
这就是一个矩阵，它是一个 333 行 222 列的矩阵。（到这里都应该很好理解吧）
三、矩阵的运算
两个矩阵之间支持多种运算，今天我主要讲解加、减、乘法运算。
1、加减运算
加减运算的前提是两个矩阵的行数和列数都相等（即大小形状完全一致）
然后对应位置的数直接相加减得到结果矩阵，结果矩阵的大小形状与初始两个矩阵相同，例如：
[1,14,51,4]+[1,91,98,1]=[2,105,149,5]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}+\begin{bmatrix} 1,9\\ 1,9 \\ 8,1 \end{bmatrix}=\begin{bmatrix} 2,10\\ 5,14 \\ 9,5 \end{bmatrix} 1,14,51,4 + 1,91,98,1 = 2,105,149,5
减法同理。
2、数乘运算
一个数乘一个矩阵，结果是一个矩阵，大小形状与原矩阵的相同。
具体运算过程是用这个数分别乘矩阵的每一个数，例如：
2∗[1,14,51,4]=[2,28,102,8]2* \begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}=\begin{bmatrix} 2,2\\ 8,10 \\ 2,8 \end{bmatrix} 2∗ 1,14,51,4 = 2,28,102,8
3、乘法运算
乘法运算的前提是前一个矩阵的行与后一个矩阵的列相等
假设初始矩阵 A 是一个 m∗nm*nm∗n 的矩阵，初始矩阵 B 是一个 n∗pn*pn∗p 的矩阵。
则结果矩阵 C 是一个 m∗pm*pm∗p 的矩阵，且
Ci,j=∑k=1nAi,k∗Bk,jC_{i,j}=\sum_{k=1}^{n} A_{i,k}*B_{k,j} Ci,j =k=1∑n Ai,k ∗Bk,j
有点绕，来看例子你就懂了：
[1,14,51,4]⋅[1,9,19,8,1]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}\cdot\begin{bmatrix} 1,9,1\\ 9,8,1 \end{bmatrix} 1,14,51,4 ⋅[1,9,19,8,1 ]
=[1∗1+1∗9,1∗9+1∗8,1∗1+1∗14∗1+5∗9,4∗9+5∗8,4∗1+5∗11∗1+4∗9,1∗9+4∗8,1∗1+4∗1]=\begin{bmatrix} 1*1+1*9,1*9+1*8,1*1+1*1\\ 4*1+5*9,4*9+5*8,4*1+5*1 \\ 1*1+4*9,1*9+4*8,1*1+4*1 \end{bmatrix} = 1∗1+1∗9,1∗9+1∗8,1∗1+1∗14∗1+5∗9,4∗9+5∗8,4∗1+5∗11∗1+4∗9,1∗9+4∗8,1∗1+4∗1
=[10,17,249,76,937,41,5]=\begin{bmatrix} 10,17,2\\ 49,76,9 \\ 37,41,5 \end{bmatrix} = 10,17,249,76,937,41,5
（这里没看懂可以多看几次，自己举个例子）
注意：矩阵乘法不支持交换律！！必须保证前一个矩阵的行与后一个矩阵的列相等！
来看这道题
直接按照上面的公式模拟就可以了。
上面的matrix结构体部分就是矩阵乘法的模板代码，可以背下来（本人在这类问题中习惯下标从 000 开始）
到此为止，你已经完成了所有铺垫知识的学习，接下来我们步入正题！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文
矩阵快速幂是一种技巧，用来优化递推类型（动态规划）的问题。
例题1
一下看到这道题，是不是觉得可以秒掉？这不是初学者就会做的题吗？
但是一看数据范围：
好吧，直接傻掉了，O(n)O(n)O(n) 的递推根本过不去！
所以就要用到今天这个算法：矩阵快速幂
我们先做一个大胆的尝试：
[1,1]∗[0,11,1]=[1,2]\begin{bmatrix} 1,1\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 1,2\end{bmatrix} [1,1 ]∗[0,11,1 ]=[1,2 ]
然后
[1,2]∗[0,11,1]=[2,3]\begin{bmatrix} 1,2\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 2,3\end{bmatrix} [1,2 ]∗[0,11,1 ]=[2,3 ]
还没看出来？再来一个：
[2,3]∗[0,11,1]=[3,5]\begin{bmatrix} 2,3\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 3,5\end{bmatrix} [2,3 ]∗[0,11,1 ]=[3,5 ]
⋯\cdots⋯
我们发现 111 行 222 列的那个矩阵里面的值就是斐波那契数列（即 FFF 数组）！！！
总结一个规律，求第 kkk 项，不就是用[1,1]\begin{bmatrix} 1,1\end{bmatrix}[1,1 ] 乘上 [0,11,1]k−1\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}^{k-1}[0,11,1 ]k−1，再取出 111 行 222 列的矩阵的第一个数吗？
接下来的问题是不是就来到了如何求 [0,11,1]k−1\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}^{k-1}[0,11,1 ]k−1 吗？
可以使用快速幂！！！
矩阵快速幂！！！
看模板代码之前，还要引入一个概念：单位矩阵（相当于累乘器初始化的 111）
它的主对角线为 111，其余地方为 000。（可以自己举几个例子，发现不管它乘什么矩阵，结果都是原来的矩阵）
和正常快速幂没什么区别，就是做运算的底数是矩阵而已。
那么我们就可以解决上面那道例题了，主函数部分：
复杂度：O(k3logn)O(k^3log n)O(k3logn) kkk 为矩阵的行/列数，可忽略。
是不是特别简单？
可能有读者看到这里会问了，如何知道那个放到快速幂中的 MMM 矩阵是什么呢？每道题的这个矩阵都一样吗？
别急，通过接下来的这道例题，你会明白如何得到这个 mmm 矩阵。
例题2
这道题看起来和刚刚那道题很像，只是多了个系数。
还是按照刚刚的思路，我们一起来推理一下 mmm 矩阵。
首先我们要先有一个矩阵（向量），里面存储了我们想要的信息。
这道题我们想知道什么呢？
首先肯定是当前这一项 aka_kak ， 然后还有什么？
我们需要知道下一项，是不是要知道它前面的两项？所以还要存储一个上一项 ak−1a_{k-1}ak−1
[ak−1,ak]\begin{bmatrix} a_{k-1},a_k\end{bmatrix} [ak−1 ,ak ]
这个向量的初始数据是 [x,y]\begin{bmatrix} x,y\end{bmatrix}[x,y ]（kkk 从 222 开始）
这样就定义好了，就像定义一个状态。接下来要推理 mmm 矩阵。
mmm 矩阵一定是一个行数等于列数的矩阵。
因为它要能和这个向量相乘，需要满足行数和列数都等于这个向量的数据个数（在这里为 222）
因此 mmm 矩阵长这样：
[?,??,?]\begin{bmatrix} ?,?\\ ?,? \end{bmatrix} [?,??,? ]
接下来我们看看如何设定 mmm 矩阵使得数据能递推下去，即满足下面这个式子：
[ak−1,ak]∗[?,??,?]=[ak,ak+1=p∗an−1+q∗an−2]\begin{bmatrix} a_{k-1},a_k\end{bmatrix}*\begin{bmatrix} ?,?\\ ?,? \end{bmatrix}=\begin{bmatrix} a_k,a_{k+1}=p*a_{n-1}+q*a_{n-2}\end{bmatrix} [ak−1 ,ak ]∗[?,??,? ]=[ak ,ak+1 =p∗an−1 +q∗an−2 ]
不难发现左上角填 000，左下角填 111，右上角填 qqq，右下角填 ppp：
[0,q1,p]\begin{bmatrix} 0,q\\ 1,p \end{bmatrix} [0,q1,p ]
这道题基本就做完了。
读者可以尝试自己推导例题一的矩阵。
掌握较熟练后，还可以思考如何求斐波那契前 nnn 项和，前 nnn 项平方和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
拓展例题
最后来看例题3
这道题看上去非常吓人，有读者可能会考虑高精度，但发现 nnn 最大有 101810^{18}1018，不可行。
考虑 dp。
设 dp[i]dp[i]dp[i] 表示考虑加到第 iii 个数的结果对 mmm 取模，不难得到状态转移方程：
dpi=dpi−1∗10x+idp_i=dp_{i-1}*10^x+i dpi =dpi−1 ∗10x+i
其中 xxx 表示 iii 是几位数。
考虑矩阵快速幂优化。
在这里直接给出递推式，请读者自行推演：
[dpi,i+1,1]∗[10x,0,01,1,00,1,1]\begin{bmatrix} dp_i,i+1,1 \end{bmatrix}*\begin{bmatrix} 10^x,0,0\\ 1,1,0 \\ 0,1,1 \end{bmatrix} [dpi ,i+1,1 ]∗ 10x,0,01,1,00,1,1
发现 10x10^x10x 会变化，考虑做多次矩阵快速幂，每次做同样位数的范围。
细节比较多，具体看代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结语
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
终于肝完了，矩阵快速幂还是挺实用的。
其实它类似于一类构造题，需要自己多多练习和领悟。
本文可能有许多没讲懂或没讲全的内容，深感抱歉，但实在是能力有限欢迎提出修改建议。
有帮助，赞一个