查看“︁05-算法模板/05-矩阵快速幂”︁的源代码


== 模板 ==

[https://oj.33dai.cn/p/P1939 P1939. 矩阵加速（数列）]

已知一个数列 <math>a</math>，满足：

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

求 <math>a</math> 数列的第 <math>n</math> 项对 <math>10^9+7</math> 取余的值。

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

== 使用说明 ==

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

时间复杂度：<math>O(k^3 \log n)</math>，其中 <math>k</math> 为矩阵大小。


[[Category:算法模板]]
[[Category:三三文档]]