题解 | #又见斐波那契#

我们只需要计算$A\ast B^{(n\mathrm{/}2)}A\; *\; B^\{(n\; /\; 2)\; \}$后根据n的奇偶性来判断选择$f_{i}f\_i$还是$f_{i+1}f\_\{i+1\}$即可

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=6;
ll mod=1000000007;
ll AA[N]={
    0,1,8,4,2,1
};
ll BB[N][N]{
    {1,1,0,0,0,0},
    {1,2,0,0,0,0},
    {1,2,1,0,0,0},
    {1,5,6,1,0,0},
    {1,7,12,4,1,0},
    {1,5,8,4,2,1}
};
ll A[N],B[N][N];
void jzc(ll a[],ll b[][N],ll c[]){
    ll tem[N]={0};
    for(int i=0;i<N;i++){
        for(int k=0;k<N;k++){
            tem[i]+=(a[k]*b[k][i]);
            tem[i]%=mod;
        }
    }
    memcpy(c,tem,sizeof tem);
}
void jzcc(ll a[][N],ll b[][N],ll c[][N]){
    ll tem[N][N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                tem[i][j]+=a[i][k]*b[k][j];
                tem[i][j]%=mod;
            }
        }
    }
    memcpy(c,tem,sizeof tem);
}
int main(){
    ll nn;
    scanf("%lld",&nn);
    while(~scanf("%lld",&nn)){
    	memcpy(A,AA,sizeof AA);
    	memcpy(B,BB,sizeof BB);
	    ll n=nn/2;
	    ll ans=nn%2;
	    while(n){
	        if(n&1){
	            jzc(A,B,A);
	        }
	        jzcc(B,B,B);
	        n>>=1;
	    }
	    printf("%lld\n",A[0+ans]);
	}
}