【模板】矩阵加速（数列）
题目描述
已知一个数列 \(a\)，它满足：
\[a_x= \begin{cases} 1 & x \in\{1,2,3\}\\ a_{x-1}+a_{x-3} & x \geq 4 \end{cases} \]求 \(a\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。
输入格式
第一行一个整数 \(T\)，表示询问个数。
以下 \(T\) 行，每行一个正整数 \(n\)。
输出格式
每行输出一个非负整数表示答案。
样例 #1
样例输入 #1
3
6
8
10
样例输出 #1
4
9
19
提示
- 对于 \(30\%\) 的数据 \(n \leq 100\)；
- 对于 \(60\%\) 的数据 \(n \leq2 \times 10^7\)；
- 对于 \(100\%\) 的数据 \(1 \leq T \leq 100\)，\(1 \leq n \leq 2 \times 10^9\)。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
long long n, m;
struct Matrix {
long long matrix[521][13];
}base, ask;
Matrix operator*(const Matrix &a, const Matrix &b) {
Matrix ans;
for (long long i = 1; i <= 3; ++ i) {
for (long long j = 1; j <= 3; ++ j) {
ans.matrix[i][j] = 0;
}
}
for (long long i = 1; i <= 3; ++ i) {
for (long long j = 1; j <= 3; ++ j) {
for (long long q = 1; q <= 3; ++ q) {
ans.matrix[i][j] += a.matrix[i][q] * b.matrix[q][j];
ans.matrix[i][j] %= m;
}
}
}
return ans;
}
Matrix MatrixQuickPower(Matrix a, long long k) {
Matrix ans;
Matrix temp = a;
for (long long i = 1; i <= 3; ++ i) {
for (long long j = 1; j <= 3; ++ j) {
if (i == j) ans.matrix[i][j] = 1;
else ans.matrix[i][j] = 0;
}
}
while (k > 0) {
if (k & 1 == 1) {
ans = ans * temp;
}
temp = temp * temp;
k >>= 1;
}
return ans;
}
int main() {
int t;
cin >> t;
while (t --) {
cin >> n;
m = 1000000000 + 7;
if (n <= 3) {
cout << 1 << endl;
continue;
}
for (long long i = 1; i <= 3; i ++) {
for (long long j = 1; j <= 3; ++ j) {
base.matrix[i][j] = 0;
}
}
base.matrix[1][1] = base.matrix[3][1] = base.matrix[1][2] = base.matrix[2][3] = 1;
base = MatrixQuickPower(base, n - 3);
cout << (base.matrix[1][1] + base.matrix[2][1] + base.matrix[3][1]) % m << endl;
}
return 0;
}