题解 P1939 【【模板】矩阵加速(数列)】
解题思路
这道题目的关键之处在于构造初始矩阵,题目都告诉我们了要用矩阵加速。所以矩阵快速幂是核心所在。
如何构造
我们首先要确定目标矩阵。下面这个矩阵就是我想要的矩阵.
那么这个矩阵要怎样算出来。根据题目给出的递推式可以得到下面三个式子
通过每一项的系数可以得出初始矩阵为
然后我们就可以通过矩阵快速幂进行求解。
值得注意的是,这个矩阵的
附上代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int Mod = 1e9+7;
int T, n;
struct mat{
LL m[5][5];
}Ans, base;
inline void init() {
memset(Ans.m, 0, sizeof(Ans.m));
for(int i=1; i<=3; i++) Ans.m[i][i] = 1;
memset(base.m, 0, sizeof(base.m));
base.m[1][1] = base.m[1][3] = base.m[2][1] = base.m[3][2] = 1;
}
inline mat mul(mat a, mat b) {
mat res;
memset(res.m, 0, sizeof(res.m));
for(int i=1; i<=3; i++) {
for(int j=1; j<=3; j++) {
for(int k=1; k<=3; k++) {
res.m[i][j] += (a.m[i][k] % Mod) * (b.m[k][j] % Mod);
res.m[i][j] %= Mod;
}
}
}
return res;
}
inline void Qmat_pow(int p) {
while (p) {
if(p & 1) Ans = mul(Ans, base);
base = mul(base, base);
p >>= 1;
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
if(n <= 3) {
printf("1\n");
continue;
}
init();
Qmat_pow(n);
printf("%lld\n", Ans.m[2][1]);
}
}
/*
f[i-1] f[i]
f[i-2] ----> f[i-1]
f[i-3] f[i-2]
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
so
1 0 1
1 0 0
0 1 0
*/