RT

vjudge题目：https://vjudge.net/problem/HDU-5950#author=GPT_zh

vjudge提交记录：https://vjudge.net/solution/57739073

我用的是矩阵的思路

$\large 至为感谢，玄关$

#include <iostream>
using namespace std;
long long n;
long long a2[7][7]=//a2数组把整个矩阵给到 
{
	{1,2,1,4,6,4,1},
	{1,0,0,0,0,0,0},
	{0,0,1,4,6,4,1},
	{0,0,0,1,3,3,1},
	{0,0,0,0,1,2,1},
	{0,0,0,0,0,1,1},
	{0,0,0,0,0,0,1}
};
#define maxn 105
long long a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],d[maxn][maxn];
const long long mod=2147493647;
void chengfa(long long a[][maxn],long long b[][maxn],long long c[][maxn],long long n,long long m,long long k)//矩阵乘法函数 
{//          乘数1         乘数2          积      矩阵阶数 
	for(long long i=1;i<=n;i++)
	{
		for(long long j=1;j<=k;j++)
		{
			long long t=0;
			for(long long kk=1;kk<=m;kk++)
			{
				t+=(a[i][kk]*b[kk][j]);t%=mod;
			}
			c[i][j]=t;
		}
	}
}
void kuaisumi(long long k,long long n)//快速幂函数 
{
	//c矩阵为结果矩阵
	//a矩阵为输入矩阵
	//b是临时数组 
	while(k)
	{
		if(k&1)
		{
			//c和a乘，结果存到b里 
			chengfa(c,a,b,n,n,n);
			//把B拷过来拷到C里
			for(long long i=1;i<=n;i++)
			{
				for(long long j=1;j<=n;j++)
				{
					c[i][j]=b[i][j];
				}
			 } 
		}
		//a自乘，结果存到B 
		chengfa(a,a,b,n,n,n);
		//然后把B拷到A里 
		for(long long i=1;i<=n;i++)
		{
			for(long long j=1;j<=n;j++)
			{
				a[i][j]=b[i][j];
			}
		} 
		//k>>=1 
		k>>=1;
	}
} 
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	//根据a2数组的内容初始化A
	for(long long i=1;i<=7;i++)
	{
		for(long long j=1;j<=7;j++)
		{
			a[i][j]=a2[i-1][j-1];
		}
	}
	long long T;cin>>T;while(T--){
	//初始化 
	for(long long i=1;i<=7;i++){for(long long j=1;j<=7;j++){a[i][j]=b[i][j]=c[i][j]=d[i][j]=0;}}
	//输入 
	cin>>n>>d[2][1]>>d[1][1];
	//特判 
	if(n==1) 
	{
		cout<<d[2][1]<<'\n';continue;
	}
	if(n==2)
	{
		cout<<d[1][1]<<'\n';continue;
	}
	//初始化D其余部分（n^4~1） 
	d[7][1]=1;
	for(long long i=6;i>=3;i--) {d[i][1]=d[1][1]*d[i+1][1];d[i][1]%=mod;}
	//初始化C为单位矩阵 
	for(long long i=1;i<=7;i++) c[i][i]=1;
	//快速幂 
	kuaisumi(n-2,7);
	//乘法	 
	chengfa(c,d,b,7,7,7);
	//输出 
	cout<<b[1][1]<<'\n';
    }
	
	return 0;
}