【题解】矩阵加速

3
6
8
10

4
9
19

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=5;
const int M=1e9+7;
struct node{
	ll a[N][N]={0};
	int row,col;
};
node I;//单位矩阵

node matrixMins(node a,node b){//矩阵乘法
	node c;//答案矩阵
	c.row=a.row;
	c.col=b.col;
	int n=c.row,p=c.col,m=a.col;
	//计算矩阵乘法
	for(int i=1;i<=n;i++){
		for(int j=1;j<=p;j++){
			for(int k=1;k<=m;k++){
				c.a[i][j]+=a.a[i][k]*b.a[k][j]%M;
				c.a[i][j]%=M;
			}
		}
	}
	return c;
}
node matrixPow(node a,ll k){//矩阵的幂次方
	if(k==0){// 0次方
		return I;//矩阵的0次方是单位矩阵
	}
	node t=matrixPow(a,k/2);//求 a^{n/2} 次方
	if(k&1){//判断k是否是奇数
		return matrixMins(matrixMins(t,t),a);
	}else{//k是偶数
		return matrixMins(t,t);
	}
}
int main(){
	int t;
	node a;
	ll n;
	cin>>t;

	//处理 加速递推矩阵
	a=node{
		{
			{0},
			{0,0,0,1},
			{0,1,0,0},
			{0,0,1,1}
		},3,3
	};
	//处理 单位矩阵
	I=node{
		{
			{0},
			{0,1,0,0},
			{0,0,1,0},
			{0,0,0,1}
		},3,3
	};
	//处理数列初始值 [1 1 2 3]
	node tt={
		{
			{0},
			{0,0,1,1}
		},1,3
	};

	while(t--){
		cin>>n;
		node tmp=matrixPow(a,n);//计算A^n
		node ans=matrixMins(tt,tmp);
		cout<<ans.a[1][1]<<endl;		
	}
	return 0;
}