记录编号	256346	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]香蕉	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2016-04-30 08:41:52	内存使用	152.94 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;
LL f[20][1000010];
LL s[20];
LL g[20][20];
int id[20][2],cnt;
struct Matrix{
	LL a[42][42];
	void clear(){memset(a,0,sizeof(a));}
}A,ans;
void UPD(LL &a){if(a>=mod)a-=mod;}
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];
				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;
			UPD(g[i][0]);UPD(g[i][1]);
		}
	}
	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("Banana.in","r",stdin);
	freopen("Banana.out","w",stdout);
	scanf("%d%d",&n,&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){
		for(int k=1;k<=m;++k){
			for(int j=k+k;j<=m;j+=k){
				f[i+1][j]=f[i+1][j]+f[i][k];
				UPD(f[i+1][j]);
			}
		}
		for(int j=1;j<=m;++j){
			s[i+1]=s[i+1]+f[i+1][j];
			UPD(s[i+1]);
		}
	}
	build_Matrix();
	A=pow_mod(A,n-1);ans=ans*A;
	LL S=(ans.a[1][1]-ans.a[1][2]+mod)%mod;
	printf("%lld\n",S);
	return 0;	
}