矩阵递推
用于快速求没有通项公式或通项公式不方便的数列递推式的第\(k\)项值。
时间复杂度 \(O(n^3\log k)\)，其中\(n\)为矩阵大小。
基于矩阵乘法和矩阵快速幂实现。
难点在于构造\(base\)矩阵。
特点：
- 类似线性递推。（包括有向图上的递推等等）
- 转移次数\(10^9\)左右。
- 决策点较少。（常数）
矩阵构造
例1：
求\(f(n)\)：
例2：
求\(f(n)\)：
例3：
求\(f(n)\)：
例4：
求\(S(n)=\sum_{i=1}^nf(i)\)：连续幂次和
连续幂次和
- 给定一个$ n\times n\(的矩阵\)A\(和一个正整数\)k\(，求\)\sum_{i=1}kAi$。
使用分治法：
每次分治时计算一下\(mid\)，递归计算 \(\sum_{i=1}^{mid}A^i\)，通过快速幂得出\(A^{mid}\)，另一半可以直接得出。（当\(k\)为奇数时还需要计算\(A^k\)）
时间复杂度\(O(n^3\log^2k)\)。
有向图中求合法路径方案数
- 给出一张 \(n\) 个点，\(m\)条边的有向图，每次询问从 \(s\)恰好\(k\)步走到\(e\)的方案数，重边视作一条路径，每条边可重复走。
我们可以将这个问题转化为一个矩阵乘法的问题。
具体来说，我们可以用一个\(n\times n\)的矩阵\(G\)来表示有向图的邻接矩阵，其中$ G[i][j]\(表示从\)i\(点到\)j$ 点的边的条数。
那么我们可以用\(G\)的\(k\)次幂来表示从任意一点恰好走\(k\)步到达另一点的方案数，即\(G^k[i][j]\) 表示从\(i\)点恰好走\(k\)步到达$j $点的方案数。
这是因为矩阵乘法的定义就是按照中间点进行求和，即\(G^k[i][j] = \sum G^{k-1}[i][w] * G[w][j]\)，其中\(w\)是任意一个中间点。这样就相当于枚举了所有可能的路径。
因此，我们只需要求出\(G\)的\(k\)次幂，然后取\(G^k[s][e]\)即可得到答案。而求矩阵的高次幂就可以用矩阵快速幂来优化时间复杂度。
时间复杂度也是\(O(n^3\log k)\)，比基于动态规划的\(O(kn^3)\)优秀许多。
- 给出一张 \(n\) 个点，\(m\)条边的有向图，每次询问从 \(s\)不超过\(k\)步走到\(e\)的方案数，重边视作一条路径，每条边可重复走。
实际上就是前两个的结合，我们只需要累加这张图的邻接矩阵的\(1\)到\(k\)次幂就可以得到最终答案。而累加可以通过上文的矩阵的连续幂次和实现。