解决矩阵加速首先要解决矩阵快速幂，不会的话可以去做P3390。
其次关键是如何构造加速矩阵，矩阵乘法首先是要会的，不熟悉的话可以去问问度娘。
下面先附上矩阵乘法的代码
矩阵乘法代码
juzheng operator* (juzheng& t1, juzheng& t2) {
juzheng t3;
memset(t3.a, 0, sizeof(t3.a));
for(int k = 0; k < 3; k++){
for(int i = 0; i < 3; i++){ // 行
for(int j = 0; j < 3; j++){
t3.a[i][j] = (t3.a[i][j] % mods + t1.a[i][k] * t2.a[k][j] % mods) % mods;
}
}
}
return t3;
}
矩阵加速公式
为什么这样构造公式
上面的加速公式是由以下公式转化而来的
F[i] = F[i - 1] * 1 + F[i - 2] * 0 + F[i - 3] * 1
F[i - 1] = F[i - 1] * 1 + F[i - 2] * 0 + F[i - 3] * 0
F[i - 2] = F[i - 1] * 0 + F[i - 2] * 1 + F[i - 3] * 0
这样再结合快速幂就可以写出完整代码了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mods = 1e9 + 7;
LL m[3][3] = {
1, 1, 0,
0, 0, 1,
1, 0, 0
};
struct juzheng{
LL a[3][3];
juzheng(){ // 初始化
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
a[i][j] = m[i][j];
}
}
}
inline void build(){ // 构造初始矩阵
/*
1 1 1
0 0 0
0 0 0
*/
for(int i = 1; i < 3; i++){
for(int j = 0; j < 3; j++){
a[i][j] = 0;
}
}
for(int i = 0; i < 3; i++){
a[0][i] = 1;
}
}
void print(){ // 打印矩阵
//ofstream cout("q1.out");
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
cout<<a[i][j];
if(j == 2)
cout<<endl;
else
cout<<" ";
}
}
}
};
juzheng operator* (juzheng& t1, juzheng& t2) {
juzheng t3;
memset(t3.a, 0, sizeof(t3.a));
for(int k = 0; k < 3; k++){
for(int i = 0; i < 3; i++){ // 行
for(int j = 0; j < 3; j++){
t3.a[i][j] = (t3.a[i][j] % mods + t1.a[i][k] * t2.a[k][j] % mods) % mods;
}
}
}
return t3;
}
int main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
if(n <= 3){
cout << "1" << endl;
continue;
}
int t = n - 3;
juzheng ans, tt;
ans.build();
while(t){
if(t & 1)
ans = ans * tt;
tt = tt * tt;
t = t >> 1;
}
cout << ans.a[0][0] << endl;
}
return 0;
}
