矩阵快速幂小结
矩阵
并不想扯什么高端线代的内容因为我也不会
定义
由$n \times m$个数$a_{ij}$排成的$n$行$m$列的数表称为$n$行$m$列的矩阵，简称$n \times m$矩阵。
$$
a =
\begin{bmatrix}
a_{11} & a_{12} & \dots a_{1m} \\
a_{21}, & \dots & \dots \\
a_{31}, & \dots & \dots \\
a_{41} & \dots & a_{nm}
\end{bmatrix}
$$
运算
这里只讲加法减法和乘法，其他的例如矩阵求逆等与本文内容出入较大，有兴趣的可以自己学习
加法
注意，只有行列均相同的矩阵才有加法！
运算也比较简单，把对应位置的数相加得到一个新的矩阵，即为答案
例如
$$
\begin{bmatrix} 1 & 1 & 2 \\ 1 & 0 & 1 \end{bmatrix}
+
\begin{bmatrix} 2 & 3 & 3 \\ 3 & 3 & 2 \end{bmatrix}
=
\begin{bmatrix} 3 & 4 & 5 \\ 4 & 3 & 3 \end{bmatrix}
$$
加法满足以下运算律
$a + b = b + a$
$(a + b) + c = a + (b + c)$
减法
与加法同理。
乘法
这才是重点！！
两个矩阵能进行乘法的前提条件是：一个矩阵的行数等于另一个矩阵的列数
形式化的来说，若$a$是$i \times k$的矩阵，那么$b$必须是$k \times j$的矩阵！
他们相乘得到的$c$是$i \times j$的矩阵
其中$c_{ij} = \sum_{i = 1}^n a_{ik} * b_{kj}$
比如
$$
\begin{bmatrix} 1 & 2\\ 2 & 3 \end{bmatrix}
\times
\begin{bmatrix} 2 & 4 & 5 \\ 3 & 4 & 3 \end{bmatrix}
=
\begin{bmatrix} 8 & 12 & 11 \\ 13 & 20 & 19 \end{bmatrix}
$$
乘法满足结合律，左分配律，右分配律，即
$(a \times b) \times c = a \times (b \times c)$
$(a + b) \times c = a \times c + b \times c$
$c(a + b) = c \times a + c \times b$
千万注意！矩阵乘法不满足交换律！(很多情况下交换之后都不能相乘)
矩阵快速幂
因为矩阵有结合律，因此我们可以把整数的快速幂推广的矩阵上面
同样是利用二进制倍增的思想，不难得到以下代码
其中的base，代表的是单位矩阵，也就是除了对角线全为$1$，其他位置都为$0$的矩阵，可以证明任意矩阵乘单位矩阵都等于自身
显然矩阵快速幂的复杂度为$o(n^3 log k)$
#include<cstdio>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int n;
ll k;
struct matrix {
int m[101][101];
matrix operator * (const matrix &rhs) const {
matrix ans = {};
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
(ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;
return ans;
}
};
matrix fastpow(matrix a, ll p) {
matrix base;
for(int i = 1; i <= n; i++) base.m[i][i] = 1;//构造单位矩阵
while(p) {
if(p & 1) base = base * a;
a = a * a; p >>= 1;
}
return base;
}
int main() {
scanf("%d %lld", &n, &k);
matrix a;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &a.m[i][j]);
a = fastpow(a, k);
for(int i = 1; i <= n; i++, puts(""))
for(int j = 1; j <= n; j++)
printf("%d ", a.m[i][j]);
return 0;
}
应用
矩阵快速幂最常见的应用就是优化递推啦
还是从最常见的斐波那契数列说起吧。
众周所知，斐波那契数列的递推公式为$$f_{n} = f_{n - 1} + f_{n - 2}, f_1 = 1, f_2 = 1$$
一般来说，这种看起来长得很萌简单，只与自身的函数值有关(可能带几个常数)的式子，一般都可以用矩阵快速幂来加速。
当然，如果你想找刺激，可以学一下这玩意儿
矩阵快速幂具体是怎么加速递推的呢？
首先我们把斐波那契数列写成矩阵的形式，因为$f_n$的取值与$f_{n - 1}, f_{n - 2}$这两项有关，因此我们需要同时保留这两项的值，我们不难得到一个$2 \times 1$的矩阵
$$
\begin{bmatrix}
f_{n} \\
f_{n - 1}
\end{bmatrix}
$$
现在我们要进行递推，也就是得到这样一个矩阵
$$
\begin{bmatrix}
f_{n + 1} \\
f_{n}
\end{bmatrix}
$$
展开
$$
\begin{bmatrix}
f_{n} + f_{n - 1} \\
f_{n}
\end{bmatrix}
$$
观察一下，上面的一项需要用到$f_{n}$和$f_{n - 1}$，下面的一项只需要用到$f_n$
同时结合上面的矩阵乘法的定义，我们不难得到一个转移矩阵
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}
\begin{bmatrix} f_{n} \\ f_{n - 1}\\ \end{bmatrix}
=
\begin{bmatrix} f_{n} + f_{n - 1} \\ f_{n}\\ \end{bmatrix}
$$
这样我们乘一次即可递推到下一项。
但是这样好像并没有什么卵用啊，复杂度上还多了个矩阵相乘
嘿嘿
不要忘了，我们前面可以讲过矩阵有结合律的！
这样的话我们只需要把转移矩阵自乘$n - 1$次，然后再与初始矩阵相乘，就能得到答案矩阵啦！
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
ll k;
struct matrix {
int m[101][101], n;
matrix() {
memset(m, 0, sizeof(m));
n = 2;
}
matrix operator * (const matrix &rhs) const {
matrix ans;
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
(ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod;
return ans;
}
};
matrix fastpow(matrix a, ll p) {
matrix base;
for(int i = 1; i <= base.n; i++) base.m[i][i] = 1;//鏋勯€犲崟浣嶇煩闃?
while(p) {
if(p & 1) base = base * a;
a = a * a; p >>= 1;
}
return base;
}
int main() {
scanf("%lld", &k);
matrix a;
a.m[1][1] = 1; a.m[1][2] = 1;
a.m[2][1] = 1; a.m[2][2] = 0;
a = fastpow(a, k - 1);
printf("%d", a.m[1][1]);
return 0;
}