矩阵快速幂

模板库

地址

$F_n=F_{n-1}+F_{n-3}$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n;
const LL MOD = 1e9+7;
struct Matrix{
    LL mat[5][5];
    Matrix(){
        memset(mat,0,sizeof(mat));
    }
}BASE,A;
Matrix operator * (const Matrix &X,const Matrix &Y){
    Matrix re;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            for(int k=1;k<=3;k++){
                re.mat[i][j]+=X.mat[i][k]*Y.mat[k][j]%MOD;
                re.mat[i][j]%=MOD;
            }
        }
    }
    return re;
}
void DEBUG(Matrix P){
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            printf("%d ",P.mat[i][j]);
        }
        puts("");
    }
}
Matrix qpow(const Matrix &x,LL k){
    Matrix mul=x;
    Matrix re;
    re.mat[1][1]=re.mat[2][2]=re.mat[3][3]=1;
    for(LL i=1;i<=k;i<<=1){
        if(i&k)
            re=mul*re;
        mul=mul*mul;
    }
    return re;
}
int main(){
    BASE.mat[1][1]=1;
    BASE.mat[1][3]=1;
    BASE.mat[2][1]=1;
    BASE.mat[3][2]=1;
    A.mat[1][1]=A.mat[2][1]=A.mat[3][1]=1;
    int kase;
    scanf("%d",&kase);
    while(kase--){
        scanf("%lld",&n);
        if(n<=3)
            puts("1");
        else
            printf("%lld\n",(qpow(BASE,n-3)*A).mat[1][1]);
    }
    return 0;
}