C++(clang++11) 解法, 执行用时: 597ms, 内存消耗: 8200K, 提交时间: 2021-02-08 21:41:42

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const LL m=998244353;
struct mat{
	int n,m;
	LL g[8][8];
	mat(int x,int y){
		n=x;m=y;
		memset(g,0,sizeof(g));
	}
};
mat operator*(mat ma, mat mb) {
    mat ret(ma.n,mb.m);
	for(int i=1;i<=ret.n;++i)
	for(int j=1;j<=ret.m;++j){
		for(int k=1;k<=ma.m;++k)
		ret.g[i][j]=(ret.g[i][j]+ma.g[i][k]*mb.g[k][j]);
		ret.g[i][j]%=m;
	}
	return ret;
}

struct mat1{
	int n,m;
	LL g[3][3];
	mat1(int x,int y){
		n=x;m=y;
		//memset(g,0,sizeof(g));
	}
};
mat1 operator*(mat1 ma, mat1 mb) {
    mat1 ret(ma.n,mb.m);
	for(int i=1;i<=ret.n;++i)
	for(int j=1;j<=ret.m;++j){
		ret.g[i][j]=0;
		for(int k=1;k<=ma.m;++k)
		ret.g[i][j]=(ret.g[i][j]+ma.g[i][k]*mb.g[k][j]);
		ret.g[i][j]%=m;
	}
	return ret;
}
mat1 cc(2,2);
mat1 anss(2,2);
mat1 aa(1,2);

void solve(LL n){
	if(n==0){
		printf("0\n");return;
	}
	if(n==1){
		printf("1\n");return;
	}
	
	cc.g[1][1]=cc.g[1][2]=cc.g[2][1]=1;cc.g[2][2]=0;
	n--;
	anss.n=anss.m=2;
	anss.g[1][1]=anss.g[2][2]=1;anss.g[1][2]=anss.g[2][1]=0;
	while(n){
		if(n&1)anss=anss*cc;
		cc=(cc*cc);n>>=1;
	}
	aa.g[1][1]=aa.g[1][2]=1;
	anss=(aa*anss);
	printf("%lld\n",anss.g[1][1]*anss.g[1][2]%m);
}
char s[30];
__int128 n=0;LL a1,a2,a3,x,y,z;
int main(){
	scanf("%s",s);int ls=strlen(s);
	for(int i=0;i<ls;i++)n=n*10+s[i]-'0';
	
	scanf("%lld%lld%lld%lld%lld%lld",&a1,&a2,&a3,&x,&y,&z);
	//cout<<n<<endl;
	mat c(7,7);
	c.g[1][1]=x*x%m; c.g[2][1]=y*y%m; c.g[3][1]=z*z%m; c.g[4][1]=2*x*y%m; c.g[5][1]=2*x*z%m; 
	c.g[6][1]=2*y*z%m;
	c.g[1][2]=1; c.g[2][3]=1; 
	c.g[1][4]=x; c.g[4][4]=y; c.g[5][4]=z;
	c.g[2][5]=y; c.g[4][5]=x; c.g[6][5]=z;
	c.g[4][6]=1;
	for(int i=1;i<=6;i++)c.g[i][7]=c.g[i][1];
	c.g[7][7]=1;
	if(n==0){
		cout<<0;
	}
	else if(n==1){
		cout<<a1*a1%m;
	}
	else if(n==2){
		cout<<(a1*a1+a2*a2)%m;
	}
	else{
		n-=3;
		mat ans(7,7);
		for(int i=1;i<=7;i++)ans.g[i][i]=1;
		while(n){
			if(n&1)ans=(ans*c);
			c=(c*c);n>>=1;
		}
		mat a(1,7);
		a.g[1][1]=a3*a3%m; a.g[1][2]=a2*a2%m; a.g[1][3]=a1*a1%m;
		a.g[1][4]=a3*a2%m; a.g[1][5]=a3*a1%m; a.g[1][6]=a2*a1%m;
		a.g[1][7]=(a.g[1][1]+a.g[1][2]+a.g[1][3])%m;
		ans=(a*ans);
		cout<<ans.g[1][7];
	}
	cout<<endl;
	int qt;
	scanf("%d",&qt);
	while(qt--){
		scanf("%lld",&x);
		solve(x);
	}
	return 0;
}