目录

• 1. 前言
• 2. 矩阵快速幂
• 3. 例题
• 4. 总结

1. 前言

本篇文章是作者学习矩阵时候的一些笔记。

注意作者是个 OIer，因此并不会涉及到专业的线性代数知识（或者说是极少）。

前置知识：矩阵定义+矩阵乘法，正整数快速幂。

2. 矩阵快速幂

我们知道复数（或者简单点，实数）中有幂的定义：

对于 /(a /in C/)，将 /(a /times a /times … /times a/)（共 /(n/) 个 /(a/)）记作 /(a^n/)。

因此仿照这个定义，矩阵中的幂的定义如下：

对于一个 /(k /times k/) 大小的矩阵 /(A/)，将 /(AAAA…A/)（共 /(n/) 个 /(A/)）记作 /(A^n/)。

需要注意的是 /(A/) 的行数与列数需要相同，否则不满足矩阵乘法的要求。

那么我们朴素计算 /(A^n/)，复杂度是 /(O(k^3n)/)。

考虑如何优化呢？

回想一下正整数快速幂的做法：利用结合律，将 /(a^b/) 中的 /(b/) 按二进制位拆掉做到 /(O(/log b)/) 的复杂度。

由于矩阵也满足结合律，因此我们也可以利用结合律，将指数 /(b/) 拆成二进制运算，这样就可以做到 /(O(k^3 /log b)/) 的复杂度（/(k/) 是矩阵大小）。

模板题链接：P3390 【模板】矩阵快速幂

Code：

/*
========= Plozia =========
    Author:Plozia
    Problem:P3390 【模板】矩阵快速幂
    Date:2021/6/1
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 100 + 10, P = 1e9 + 7;
int n;
LL k;

struct Matrix
{
    LL a[MAXN][MAXN];
    Matrix operator *(const Matrix &fir)
    {
        Matrix c; memset(c.a, 0, sizeof(c.a));
        for (int i = 1; i <= n; ++i)
            for (int k = 1; k <= n; ++k)
            {
                int r = a[i][k];
                for (int j = 1; j <= n; ++j) { c.a[i][j] += r * fir.a[k][j]; c.a[i][j] %= P; }
            }
        return c;
    }
}a;

LL Read()
{
    LL sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }

Matrix ksm(Matrix a, LL b, LL p)
{
    Matrix ans;
    for (int i = 1; i <= n; ++i)
            ans.a[i][i] = 1;
    for (; b; b >>= 1, a = a * a)
        if (b & 1) ans = ans * a;
    return ans;
}

int main()
{
    n = Read(), k = Read();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            a.a[i][j] = Read();
    Matrix ans = ksm(a, k, P);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j) printf("%lld ", ans.a[i][j]);
        printf("/n");
    }
    return 0;
}

3. 例题

矩阵快速幂一个很重要的应用就是加速递推。

举个例子：P1962 斐波那契数列

如果采用直接递推的 /(O(n)/) 方式，将会获得 60pts 的好成绩。

那么如何得到 100pts 呢？这个时候就需要矩阵出场了。

由式子 /(F_n=F_{n-2}+F_{n-1}/)，我们可以构造矩阵 /(/begin{bmatrix}F_{n-1}&F_n/end{bmatrix}/)，则要推出的矩阵是 /(/begin{bmatrix}F_{n}&F_{n+1}/end{bmatrix}/)。

对要推出的矩阵做一个变形：/(/begin{bmatrix}0 /times F_{n-1} + 1 /times F_{n}&1 /times F_{n-1} + 1 /times F_{n}/end{bmatrix}/)。

于是我们可以构造出这样的转移矩阵：/(/begin{bmatrix}0&1//1&1/end{bmatrix}/)。

于是 /(/begin{bmatrix}F_{n-1}&F_n/end{bmatrix}/begin{bmatrix}0&1//1&1/end{bmatrix}=/begin{bmatrix}F_{n}&F_{n+1}/end{bmatrix}/)

现在已知初状态矩阵 /(/begin{bmatrix}F_1&F_2/end{bmatrix}/)，因此如果我们要求 /(F_n(n /geq 3)/) 的值，我们就可以计算下面的结果，然后取第二个元素：

/[/begin{bmatrix}F_1&F_2/end{bmatrix}/begin{bmatrix}0&1//1&1/end{bmatrix}^{n-2}
/]

发现这个可以用矩阵快速幂优化。

注意当 /(n<3/) 的时候直接输出 /(F_{n}/)。

4. 总结

• 矩阵快速幂：利用矩阵乘法的结合律减少复杂度。
• 应用：利用矩阵优化式子来加速递推。