# 【luogu P1939 【模板】矩阵加速（数列）】 题解

f[x+1] =1f[x] + 0f[x-1] + 1f[x-2]
f[x] = 1
f[x] + 0f[x-1] + 0f[x-2]
f[x-1] = 0f[x] + 1f[x-1] + 0*f[x-2]

1 1 0
0 0 1
1 0 0

``````#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 110;
const int mod = 1000000007;
struct Matrix{
ll m[maxn][maxn];
}A, E, Ans;
ll n, q[maxn];
Matrix mul(Matrix A, Matrix B)
{
Matrix C;
for(int i = 1; i <= 3; i++)
for(int j = 1; j <= 3; j++)
{
C.m[i][j] = 0;
for(int k = 1; k <= 3; k++)
C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j] % mod) % mod;
}
return C;
}
Matrix qpow(Matrix A, ll k)
{
Matrix S = E;
while(k)
{
if(k & 1) S = mul(S, A);
A = mul(A, A);
k = k >> 1;
}
return S;
}
int main()
{
cin>>n;
E.m[2][2] = 1;
E.m[1][1] = 1;
E.m[3][3] = 1;
A.m[1][1] = 1;
A.m[1][2] = 1;
A.m[2][3] = 1;
A.m[3][1] = 1;

for(int i = 1; i <= n; i++)
{
ll k;
cin>>k;
Ans = qpow(A, k);
cout<<Ans.m[1][2]<<endl;
}
return 0;
}``````

【luogu P1939 【模板】矩阵加速（数列）】 题解

(0)
(0)

0条