【算法原理】矩阵乘法

一般是矩阵乘法 + 快速幂，结合 \(dp\)

普通矩阵乘法：

矩阵乘法有结合律，无交换律。
因此在计算一长串矩阵相乘的时候，可以依据计算难度选择计算顺序，从而优化计算时间。

板子

例题

1304. 佳佳的斐波那契

https://www.acwing.com/problem/content/1306/
经典 \(Fibonacci\) 求和优化。

关键在于构造一个只有常量的系数矩阵 \(A\)，然后利用结合律优化计算矩阵乘的过程。

如下图，系数存在变量，所以要做一些变换：

有点高中数学那味了。
因此要维护的信息就是：

die码：

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 4;
int n, m;

void mul(int c[][N], int a[][N], int b[][N])  {// c = a * b
    static int t[N][N];
    memset(t, 0, sizeof t);

    for (int i = 0; i < N; i ++ ) {
        for (int j = 0; j < N; j ++ ) {
            for (int k = 0; k < N; k ++ ) {
                t[i][j] = (t[i][j] + (ll)a[i][k] * b[k][j]) % m;
            }
        }
    }
    memcpy(c, t, sizeof t);
}

int main() {
    cin >> n >> m;
    // {fn, fn+1, sn, pn}
    // pn = n * sn - tn
    int f1[N][N] = {1, 1, 1, 0};
    int a[N][N] = {
        {0, 1, 0, 0},
        {1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 0, 1},
    };

    int k = n - 1;
    // 快速幂
    while (k) {
        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        k >>= 1;
    }
    cout << (((ll)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;
}

//1：00：00

Ref

\(AcWing\) 提高课

维基百科

从零开始的矩阵乘法

矩阵加速图上问题学习笔记