33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:35Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 模板 ==

[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:三三文档]]

05-算法模板/05-矩阵快速幂 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档