Aimee

矩阵加速递推的模板了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
#define ll long long
using namespace std;
const ll mod = 1e9+7;
ll n, a, b, m, p;
int t;
struct re {
    int rec[51][51];
} ans, tem, org;
re tim(re x, re y) {
    re tem;
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= 3; ++j) {
            tem.rec[i][j] = 0;
            for (int k = 1; k <= 3; ++k) {
                tem.rec[i][j] += (x.rec[i][k] % mod) * (y.rec[k][j] % mod);
                tem.rec[i][j] %= mod;
            }
        }
    }
    return tem;
}
long long deal(){
    int x=n;
    if(x<=3){
        return 1;
    }
    tem=org;
    memset(ans.rec,0,sizeof(ans.rec));
    ans.rec[1][1]=ans.rec[2][2]=ans.rec[3][3]=1;
    while(x){
        if(x&1){
            ans=tim(ans,tem);   
        }
        x>>=1;
         tem=tim(tem,tem);
    }
    return ans.rec[2][1]%mod;
}
signed main() {
    scanf("%d",&t);
    org.rec[1][1]=org.rec[1][3]=org.rec[2][1]=org.rec[3][2]=1;
    while(t--){
        scanf("%d",&n);
        cout<<deal()<<endl; 
    } 
    return 0;
}