OI算法——矩阵加速递推
在开始之前，确保你至少已经学会了矩阵乘法的计算方法。
矩阵加速递推（后边简称矩阵递推）充分利用了初等矩阵的性质，可以将原本耗时间费空间的函数递归、优化但复杂度较高的记忆化搜索进一步加速为复杂度仅
矩阵乘法是如何起作用的
初等矩阵——概念及用法，花一点篇幅来复习一下：
初等行变换：
- 交换矩阵某两行
- 将某一行的元素全部乘以一个非零数
- 将某一行的非零倍加到另一行上
非常简单，甚至我们化简多元方程式都会用到上边的变换。事实上，如果把一次方程组的系数和常数项按一定顺序排列起来，将会得到一个系数矩阵，系数矩阵经过一系列化简和反代也可以解出原方程组的解。
考虑一个单位矩阵
那么一个初等矩阵就是单位矩阵只进行一次初等行变换得到的矩阵。进行变换法则的第几条就是第几类初等矩阵。一般来说，矩阵递推里的转移矩阵不属于初等矩阵，因为它通常会经过不止一次的初等行变换。递推时，如果初始矩阵是一列数，那么一般选择左乘转移矩阵；如果是一行数字，就选择右乘。（具体情况具体分析）
接下来进入正题：
假如有下边这个递推关系
初始情况下，我们向矩阵中放入两个元素：
矩阵结构体
函数I()的功能是构造单位矩阵，后面会涉及到定义它的原因。整体思路就是定义二维数组存放矩阵元素，声明时对内部元素自动置零，以及构造单位矩阵
struct Matrix { ll mat[N + 1][N + 1];
Matrix() { memset(mat, 0, sizeof mat); }
void I() { memset(mat, 0, sizeof mat); for (int i = 1; i <= N; i++) mat[i][i] = 1; }};矩阵快速幂
和实数运算一样，矩阵自乘也可以用二进制快速幂的方式快速求解，复杂度是
下边是实数快速幂的代码（带取模）：
int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = (ll) res * a % MOD; a = a * a % MOD; b >>= 1; } return res;}原理不再赘述。如果想要把它改造成适用于矩阵的快速幂算法，我们就需要实现这两个运算：
- 矩阵乘法
- 矩阵置一
对于第一点，我们根据矩阵乘法的定义可以很轻松写出代码。一般来说，重载运算符是一个很方便的办法（注意如果重载在结构体内就需要在函数定义时加上friend友元访问权）：
Matrix operator *(const Matrix &l, const Matrix &r) { Matrix res; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { for (int k = 1; k <= N; k++) { res.mat[i][j] += (l.mat[i][k] * r.mat[k][j]); res.mat[i][j] %= MOD; } } }}那么“置一”是什么呢？
相当于实数快速幂里的int res = 1;，试想一个全新定义的零矩阵（元素全为零）拿去计算乘法，最终的结果总会是零。因此我们就需要找到和 I()函数用于将矩阵变为一个主对角线元素全为
类比实数快速幂，矩阵快速幂是这样的：
Matrix qpow(Matrix a, int b) { Matrix res; res.I(); while (b) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}此时就不能图省事用*=运算符了（除非你另外重载，但这样会更麻烦）
转移矩阵的构造
转移矩阵可谓是矩阵递推题目的灵魂所在，合理地构造转移矩阵可以达到事半功倍的效果。接下来通过几个例子来深入探究转移矩阵的构造方法：
洛谷 P1962 斐波那契数列
题目传送门：这里
题目难度：普及+/提高
大家都知道，斐波那契数列是满足如下性质的一个数列：
请你求出
的值。 输入一行一个正整数
输出一行一个整数表示答案。
数据范围：
对于
的数据， ； 对于
的数据， 。
正如这头图所示，我们的初始矩阵是 嘎嘎好用是不是
首先，要求出某一项，就必须明确它的前两项。因此我们让初始矩阵填上
所谓左移，就是让
第二列也很简单，对原先的转移矩阵的两个元素都配上系数
于是代码就出来了（不开）：long long见祖宗
#include <bits/stdc++.h>
#define N 15using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
struct Matrix { ll mat[N][N];
Matrix() { memset(mat, 0, sizeof mat); }
void I() { memset(mat, 0, sizeof mat); for (int i = 1; i <= 2; i++) mat[i][i] = 1; }};
Matrix operator *(const Matrix &l, const Matrix &r) { Matrix res; for (int i = 1; i <= 2; i++) { for (int j = 1; j <= 2; j++) { for (int k = 1; k <= 2; k++) { res.mat[i][j] += (l.mat[i][k] * r.mat[k][j]); res.mat[i][j] %= MOD; } } } return res;}
Matrix qpow(Matrix a, ll b) { Matrix res; res.I(); while (b) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
ll n; cin >> n;
Matrix A, M; A.mat[1][1] = A.mat[1][2] = 1; M.mat[1][2] = M.mat[2][1] = M.mat[2][2] = 1;
A = A * qpow(M, n - 1);
cout << A.mat[1][1] % MOD << endl;
return 0;}总用时：
这种类型的题还有洛谷 P1349 广义斐波那契数列，同样是左移技巧，只不过转移矩阵要稍作变动。
洛谷 P1397 矩阵游戏
题目传送门：这里
题目难度：提高+/省选
题目来源：NOI 2013
NOI 2012 和 2013连着两年都考了矩阵递推，真的强！
婷婷是个喜欢矩阵的小朋友，有一天她想用电脑生成一个巨大的
行 列的矩阵（你不用担心她如何存储）。她生成的这个矩阵满足一个神奇的性质：若用 来表示矩阵中第 行第 列的元素，则 满足下面的递推式: 递推式中
都是给定的常数。 现在婷婷想知道
的值是多少，请你帮助她。由于最终结果可能很大，你只需要输出 除以 的余数。 输入包含一行，有六个整数
。意义如题所述。 输出包含一个整数，表示
除以 的余数。 数据范围：
这道题需要我们推一个式子，因为递推公式出现了两种情况，我们就需要两个不同的转移矩阵。假设一个为
这里出现了常数项，通常选择在初始矩阵中放入一个常量
那么在初始矩阵的第二列放上常量
同理有：
接下来根据题目描述，要想一路推到右下角的 十的一百万次方？？？太抽象了，对于这么大的幂，普通的位运算快速幂已经满足不了时限了，于是我们引入一种高级方法——十进制快速幂：
快速幂基于数字的拆位，所以我们可以选择在十进制表示下拆位运算。因此就算是十的一百万次方，应用十进制快速幂就会让复杂度降落不少，因此我们试验这个方法：
十进制矩阵快速幂：
Matrix dec_qpow(Matrix a, string b) { Matrix res; res.I(); int len = b.length(); while (len) { int p = b[len - 1] - '0'; if (p) { for (int i = 1; i <= p; i++) { res = res * a; } } for (int i = 1; i <= 10; i++) a = a * a; len--; } return res;}当然可以用二进制快速幂取代中间的循环乘幂，代码会简洁一些：
Matrix dec_qpow(Matrix a, string b) { Matrix res; res.I(); int len = b.length(); while (len) { int p = b[len - 1] - '0'; res = res * bin_qpow(a, p); a = bin_qpow(a, 10); len--; } return res;}然后我们再来算上面推出的式子，考虑到变量
#include <bits/stdc++.h>#define N 5using namespace std;
const int MOD = 1e9 + 7;
typedef long long ll;
struct Matrix { ll a[N][N];
Matrix() { memset(a, 0, sizeof a); }
void I() { a[1][1] = a[2][2] = 1; }} A, M, S;
Matrix operator *(const Matrix &l, const Matrix &r) { Matrix res; for (int i = 1; i <= 2; i++) { for (int j = 1; j <= 2; j++) { for (int k = 1; k <= 2; k++) { res.a[i][j] = (res.a[i][j] + l.a[i][k] % MOD * r.a[k][j] % MOD) % MOD; } } } return res;}
Matrix bin_qpow(Matrix a, ll b) { Matrix res; res.I(); while (b) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}
Matrix dec_qpow(Matrix a, string b) { Matrix res; res.I(); int len = b.length(); while (len) { int p = b[len - 1] - '0'; for (int i = 1; i <= p; i++) { res = res * a; } a = bin_qpow(a, 10); len--; } return res;}
string init(string s) { for (int i = s.length() - 1; i >= 0; i--) { if (s[i] == '0') s[i] = '9'; else { s[i]--; break; } } return s;}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
string n, m; ll a, b, c, d;
cin >> n >> m >> a >> b >> c >> d;
A.a[1][1] = 1, A.a[1][2] = 1; M.a[2][2] = 1, M.a[1][1] = a, M.a[2][1] = b; S.a[2][2] = 1, S.a[1][1] = c, S.a[2][1] = d;
n = init(n), m = init(m);
Matrix T = A * dec_qpow((dec_qpow(M, m) * S), n) * dec_qpow(M, m);
cout << T.a[1][1] % MOD << endl; return 0;}这段代码只能得80分，最后四个点TLE了。此时有两种解决办法，第一是卡常——将矩阵乘法的三层循环完全展开、内联函数、加法取模，可以将代码运行时间压到
矩阵递推的变式
广义矩阵乘法
相信你已经背下了矩阵乘法的模板了，为了避免遗忘，再在这里给出矩阵乘法的一般定义：假设一个
最终结果
那么是不是非得要求和和相加呢？当然不是，对于一般的矩阵乘法，才会像上边一样对乘积求和。广义矩阵乘法不仅限于上边的“对积求和”的规则，它还可以做到“对位与求位或和”。接下来探讨广义矩阵乘法所要满足的条件：
定义运算符
要想让这种运算关系能够支持递推算法，那就必须使算式
换句话说：
类比一般加法和乘法。当
支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或赞助支持！
部分内容可能已过时
