记录编号	256398	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]EX_香蕉	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	10.506 s
提交时间	2016-04-30 10:23:21	内存使用	15.64 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;

typedef unsigned long long LL;
const int mod=998244353;
int n,m,N,L,T;
LL f[2][1000010];
LL s[30];
LL g[30][30];
int id[30][2],cnt;
struct Matrix{
	LL a[52][52];
	void clear(){memset(a,0,sizeof(a));}
}A,B,ans;
Matrix operator *(const Matrix &A,const Matrix &B){
	Matrix C;C.clear();
	for(int i=1;i<=cnt;++i){
		for(int j=1;j<=cnt;++j){
			int sum=0;
			for(int k=1;k<=cnt;++k){
				C.a[i][j]=C.a[i][j]+A.a[i][k]*B.a[k][j]%mod;
				sum++;
				if(sum==10)sum=0,C.a[i][j]%=mod;
			}C.a[i][j]%=mod;
		}
	}return C;
}
Matrix pow_mod(Matrix v,int p){
	Matrix tmp;tmp.clear();
	for(int i=1;i<=cnt;++i)tmp.a[i][i]=1;
	while(p){
		if(p&1)tmp=tmp*v;
		v=v*v;p>>=1;
	}return tmp;
}
void build_Matrix(){
	for(int i=1;i<=L;++i){
		id[i][0]=++cnt;
		id[i][1]=++cnt;
	}
	for(int i=1;i<=cnt-2;++i)A.a[i+2][i]=1;
	for(int i=1;i<=L;++i){
		int j=(L+1-i);
		A.a[id[i][(j&1)^1]][cnt-1]=s[j];
		A.a[id[i][j&1]][cnt]=s[j];
	}g[0][0]=1;
	for(int i=1;i<=L;++i){
		for(int j=1;j<=i;++j){
			g[i][0]=g[i][0]+g[i-j][(j&1)^1]*s[j]%mod;
			g[i][1]=g[i][1]+g[i-j][j&1]*s[j]%mod;
			if(g[i][0]>=mod)g[i][0]-=mod;
			if(g[i][1]>=mod)g[i][1]-=mod;
		}
	}return;
}
void Get_ans(){
	for(int i=1;i<=L;++i){
		ans.a[1][id[i][0]]=g[i][0];
		ans.a[1][id[i][1]]=g[i][1];
	}return;
}
int main(){
	freopen("EX_Banana.in","r",stdin);
	freopen("EX_Banana.out","w",stdout);
	scanf("%d",&m);
	for(N=1;N<=m;N<<=1,L++);
	for(int i=1;i<=m;++i)f[1][i]=1;
	s[1]=m;
	for(int i=1;i<L;++i){
		int la=(i&1),now=(la^1);
		for(int k=1;k<=m;++k){
			if(f[la][k]){
				for(int j=k+k;j<=m;j+=k){
					f[now][j]=f[now][j]+f[la][k];
					if(f[now][j]>=mod)f[now][j]-=mod;
				}
			}
		}
		for(int j=1;j<=m;++j){
			s[i+1]=s[i+1]+f[now][j];
			f[la][j]=0;
			if(s[i+1]>=mod)s[i+1]-=mod;
		}
	}
	build_Matrix();Get_ans();
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);B=pow_mod(A,n-1);Get_ans();
		ans=ans*B;LL S=(ans.a[1][1]-ans.a[1][2]+mod)%mod;
		printf("%lld\n",S);
	}return 0;	
}