C++(g++ 7.5.0) 解法, 执行用时: 49ms, 内存消耗: 404K, 提交时间: 2022-08-16 00:17:52

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct node{
	ll num[6][6]={
       {1,1,1,1,1,1},
       {1,0,0,0,0,0},
       {0,0,1,3,3,1},
       {0,0,0,1,2,1},
       {0,0,0,0,1,1},
       {0,0,0,0,0,1}
    }; 
};
void init(node &temp){
	temp.num[0][0]=1;
	temp.num[1][0]=0;
	temp.num[2][0]=8;
	temp.num[3][0]=4;
	temp.num[4][0]=2;
	temp.num[5][0]=1;
}
node f(node a,node b){
	node temp;
	for(int i=0;i<6;++i)
		for(int j=0;j<6;++j){
			temp.num[i][j]=0;
			for(int k=0;k<6;++k)
				temp.num[i][j]+=(a.num[i][k]*b.num[k][j])%mod;
            temp.num[i][j]%=mod;
		}
	return temp;
}
int t;
ll n;
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		if(n<=1){
			printf("%lld\n",n);
			continue;
		}
		node A,ans;
		init(ans);
		--n;
		while(n){
			if(n&1)
				ans=f(A,ans);
			A=f(A,A);
			n>>=1;
		}
		f(A,ans);
		printf("%lld\n",ans.num[0][0]);
	}
} 

C++14(g++5.4) 解法, 执行用时: 247ms, 内存消耗: 468K, 提交时间: 2018-05-13 14:56:54

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const int N=2e5+5,mod=1e9+7;
mat mul(mat a,mat b)
{
	mat c(a.size(),vec(b[0].size()));
	for(int i=0;i<a.size();i++)
	{
		for(int j=0;j<b[0].size();j++)
		{
			c[i][j]=0;
			for(int k=0;k<b.size();k++)
				c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%mod)%mod;
		}
	}
	return c;
}
mat powmod(mat a,ll n)
{
	mat c(a.size(),vec(a.size()));
	for(int i=0;i<a.size();i++)
		c[i][i]=1;
	while(n)
	{
		if(n&1)
			c=mul(c,a);
		a=mul(a,a);
		n>>=1;
	}
	return c;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	mat A(6,vec(6)),x(1,vec(6));
	A={{1,1,0,0,0,0},{1,0,0,0,0,0},{1,0,1,0,0,0},{4,0,3,1,0,0},{6,0,3,2,1,0},{4,0,1,1,1,1}};
	x={{1,0,1,1,1,1}};
	ll T,n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		mat AA=powmod(A,n-1);
		mat res=mul(x,AA);
		cout<<res[0][0]<<'\n';
	}
	return 0;
}

C++ 解法, 执行用时: 137ms, 内存消耗: 420K, 提交时间: 2021-12-30 19:41:04

#include<bits/stdc++.h>
#define f(i,t) for(int i=0;i<t;i++)
using namespace std;
typedef long long ll;
typedef valarray<ll> mat;
const int k=6;
ll mod=1e9+7;
mat operator*(mat a,mat b){
    int p=b.size()==6?1:k;mat q(k*p);
    f(i,k)f(j,p){
        mat arow=a[slice(k*i,k,1)],bcol=b[slice(j,k,p)];
        q[p*i+j]=((arow%mod)*(bcol%mod)).sum()%mod;
    }
    return q;
}
mat qpow(mat a,mat b,ll n){
    while(n){if(n&1)b=a*b;a=a*a;n>>=1;}
    return b;
}
signed main(){
    cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false);
    mat a={1,1,1,1,1,1,
           1,0,0,0,0,0,
           0,0,1,3,3,1,
           0,0,0,1,2,1,
           0,0,0,0,1,1,
           0,0,0,0,0,1},b={1,0,8,4,2,1};
    int t;cin>>t;
    while(t--){ll n;cin>>n;cout<<qpow(a,b,n-1)[0]<<'\n';}
    return 0;
}