05-算法模板/05-矩阵快速幂

模板

P1939. 矩阵加速（数列）

已知一个数列 [math]\displaystyle{ a }[/math]，满足：

[math]\displaystyle{ a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} }[/math]

求 [math]\displaystyle{ a }[/math] 数列的第 [math]\displaystyle{ n }[/math] 项对 [math]\displaystyle{ 10^9+7 }[/math] 取余的值。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXR = 3, MAXC = 3;
int MOD = 1000000000 + 7;

struct Mat
{
    int r, c;
    int m[MAXR + 1][MAXC + 1];
    Mat() { memset(m, 0, sizeof(m)); }
};

Mat operator*(const Mat &a, const Mat &b)
{
    assert(a.c == b.r);
    Mat res;
    res.r = a.r, res.c = b.c;
    for (int i = 1; i <= a.r; i++)
        for (int k = 1; k <= a.c; k++)
        {
            int temp = a.m[i][k];
            for (int j = 1; j <= b.c; j++)
                res.m[i][j] = (res.m[i][j] + temp * b.m[k][j]) % MOD;
        }
    return res;
}

Mat quick_pow(Mat a, int b)
{
    assert(a.r == a.c);
    Mat res;
    res.r = res.c = a.r;
    for (int i = 1; i <= res.r; i++)
        res.m[i][i] = 1;
    while (b > 0)
    {
        if (b % 2)
            res = res * a;
        a = a * a;
        b = b / 2;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    Mat now;
    now.r = 1, now.c = 3;
    now.m[1][1] = 1, now.m[1][2] = 1, now.m[1][3] = 1;
    Mat ans;
    ans.r = ans.c = 3;
    ans.m[1][1] = 0, ans.m[1][2] = 0, ans.m[1][3] = 1;
    ans.m[2][1] = 1, ans.m[2][2] = 0, ans.m[2][3] = 0;
    ans.m[3][1] = 0, ans.m[3][2] = 1, ans.m[3][3] = 1;
    while (T--)
    {
        int x;
        cin >> x;
        Mat ans_ = quick_pow(ans, x - 1);
        Mat now_ = now * ans_;
        cout << now_.m[1][1] % MOD << "\n";
    }
    return 0;
}

使用说明

1. 根据递推式构造转移矩阵 ans（方阵）和初始向量 now（一行多列的矩阵） 2. 调用 quick_pow(转移矩阵, 幂次) 进行矩阵快速幂 3. now * ans_pow 得到结果向量

时间复杂度：[math]\displaystyle{ O(k^3 \log n) }[/math]，其中 [math]\displaystyle{ k }[/math] 为矩阵大小。