矩阵加速入门

qW__Wp · 2025-11-20 16:42:00 · 算法·理论

一、矩阵乘法

1.1 定义与运算

矩阵乘法常常指一般矩阵乘法。一个 n \times p 的矩阵 A 与一个 p \times m 的矩阵 B 相乘，得到一个 n \times m 的矩阵 P。具体地，有

举个例子：

将得到

通俗地理解，P_{i,j} 就是 A 矩阵的第 i 行与 B 矩阵的第 j 列的对应位置乘积之和。体现在代码上，就是：

for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
        for (int k = 1; k <= p; k ++) {
            c[i][j] += a[i][k] * b[k][j];
        }
    }
}

从上面可以看出，矩阵乘法 A \times B 要求矩阵 A 的列数与矩阵 B 的行数相等。

1.2 基本性质

1. 具有：

   • 结合律：(AB)C = A(BC)。
   • 分配律：A(B+C) = AB + AC、(B+C)A = BA + CA。

   这两点尤其重要。

2. 不具有：

   • 往往不具有交换律：A \times B 合法，B \times A 不一定合法。即使都合法，两者不一定相等。
   • 往往不具有消去律：满足 AB = AC 不一定有 B = C。满足 AB = 0 不一定有 A 或 B 为零矩阵。

1.3 单位矩阵

单位矩阵 I 是一个方阵，其主对角线上的元素均为 1，其余元素均为 0。即

其性质为：任何矩阵与单位矩阵相乘都得原矩阵。

1.4 矩阵快速幂

P3390 【模板】矩阵快速幂

前置芝士：快速幂

了解了矩阵乘法，矩阵快速幂就很简单了。将矩阵封装为结构体并重载乘号，然后按照普通快速幂的方法即可，时间复杂度 O(n^2 \log k)。

::::success[Code]

#include <bits/stdc++.h>
#define int long long
//#define INF 0x3f3f3f3f
#define endl '\n'

using namespace std;

const int N = 105, Mod = 1e9 + 7;

int n, k;

struct Matrix {
    int a[N][N];
    Matrix() {
        memset(a, 0, sizeof a);
    }
    void build() {
        for (int i = 1; i <= n; i ++) a[i][i] = 1;
    }
};

void Add(int &x, int y) {
    x += y; if (x >= Mod) x -= Mod;
}

Matrix operator *(const Matrix &x, const Matrix y) {
    Matrix z;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            for (int k = 1; k <= n; k ++) {
                Add(z.a[i][j], x.a[i][k] * y.a[k][j] % Mod);
            }
        }
    }
    return z;
}

signed main() {
//  freopen("", "r", stdin);
//  freopen("", "w", stdout);
//  ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    Matrix x;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cin >> x.a[i][j];
        }
    }
    Matrix ans; ans.build();
    while (k) {
        if (k & 1) ans = ans * x;
        x = x * x, k >>= 1;
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            cout << ans.a[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

::::

二、应用

一大堆题目来袭。

套路什么的，题目做多了就会了，这里先不讲。

2.1 加速递推式

P1962 斐波那契数列

::::info[省流]

::::

考虑斐波那契数列相邻两项构成的矩阵 \begin{bmatrix} F_n & F_{n-1} \end{bmatrix}。由于

所以

于是由 \begin{bmatrix} F_2 = 1 & F_1 = 1 \end{bmatrix} 进行 n - 2 次乘的操作即可得到 \begin{bmatrix} F_n & F_{n-1} \end{bmatrix}。即：

用矩阵快速幂求出 A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ {n-2}，则 F_n = A_{1,1} + A_{2,1}。

::::success[Code]

#include <bits/stdc++.h>
#define ll long long
//#define INF 0x3f3f3f3f
#define endl '\n'

using namespace std;

const int Mod = 1e9 + 7;

struct Mat {
    ll a[2][2];
    Mat () { memset(a, 0, sizeof a); }
    Mat operator*(const Mat& b) const {
        Mat res;
        for (int i = 0; i < 2; i ++) {
            for (int j = 0; j < 2; j ++) {
                for (int k = 0; k < 2; k ++) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % Mod;
                }
            }
        }
        return res;
    }
};

int fib(ll n) {
    if (n <= 2) return 1;
    Mat ans, base;
    base.a[0][0] = p, base.a[1][0] = q, base.a[1][1] = 1;
    ans.a[0][0] = ans.a[1][1] = 1;
    n -= 2;
    while (n) {
        if (n & 1) ans = ans * base;
        base = base * base, n >>= 1;
    }
    return (ans.a[0][0] + ans.a[1][0]) % Mod;
}

signed main() {
//  freopen("", "r", stdin);
//  freopen("", "w", stdout);
//  ios::sync_with_stdio(0); cin.tie(0);
    ll n; cin >> n;
    cout << fib(n);
    return 0;
}

::::

P1306 斐波那契公约数

求 \gcd(F_n,F_m)。考察了斐波那契数列的性质 \gcd(F_n,F_m) = F_{\gcd(n,m)}。笔者数学不好，就不证了。

P1349 广义斐波那契数列

灵活变化转移矩阵。考虑

于是

P1939 矩阵加速（数列）

我们希望构造矩阵 B 使

由于 a_x = 1 \cdot a_{x-1} + 0 \cdot a_{x-2} + 1 \cdot a_{x-3}，所以转移矩阵第一列为 \begin{bmatrix}1 \\ 0 \\ 1\end{bmatrix}。

同理求出转移矩阵第二、三列，最终得到

求出 B \gets B^{n-3}，答案即为 B_{1,1}+B_{2,1}+B_{3,1}。

P1397 [NOI2013] 矩阵游戏

::::info[题意]{open} 给定 n,m,a,b,c,d，对于递推式

求 F(n,m)，答案对 10^9 + 7 取模。