C++14(g++5.4) 解法, 执行用时: 1066ms, 内存消耗: 2156K, 提交时间: 2020-05-10 14:35:21

#include<bits/stdc++.h>
#define hhh printf("hhh\n"); 
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f;
const ll md=998244353;
const ll N=1e5+100;
const double eps=1e-6;
ll n,k;
struct matrix{
	ll f[210][210];
	matrix(){
		memset(f,0,sizeof(f));
	}
};
matrix mul(matrix x,matrix y)
{
	matrix z;
	ll i,j,k;
	for(j=1;j<=n;j++)
	for(k=1;k<=n;k++)
	{
		if(y.f[k][j]) for(i=1;i<=n;i++) z.f[i][j]=(z.f[i][j]+x.f[i][k]*y.f[k][j])%(md);
	}
	return z;
}
int main()
{
	scanf("%lld %lld",&n,&k);
	matrix ans,a;
	a.f[1][1]=a.f[1][2]=1;
	for(int i=k+3;i<=k*2+3;i++) a.f[i][i-k-1]=1;
	a.f[k+2][k+2]=a.f[k+2][k*2+3]=1;
	a.f[k*2+3][k+2]=1;
	for(int i=k+1;i>=2;i--)
	{
		for(int j=1;j<=k*2+3;j++) a.f[i][j]=(a.f[i+1][j]+a.f[i+1][j+1])%md;
	}
	for(int i=k*2+2;i>=k+3;i--)
	{
		for(int j=1;j<=k*2+3;j++) a.f[i][j]=(a.f[i+1][j]+a.f[i+1][j+1])%md;
	}
/*	for(int i=k+1;i>=2;i--)
	{
		for(int j=k+3;j<=k*2+3;j++) if((k+2-i+k*2+3-j)%2) a.f[i][j]=a.f[i][j]*2%md;;
	}*/
	for(int i=1;i<=k*2+3;i++) ans.f[i][i]=1;
	ll x=n;
	n=2*k+3;
/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) printf("%lld ",a.f[i][j]);
		printf("\n");
	}*/
	while(x)
	{
		if(x%2) ans=mul(ans,a);
		a=mul(a,a);
		x/=2;
	}
/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) printf("%lld ",ans.f[i][j]);
		printf("\n");
	}*/
	ll num=0;
	for(int i=2;i<=k+2;i++) num=(num+ans.f[1][i])%md;
	printf("%lld\n",num);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 997ms, 内存消耗: 1128K, 提交时间: 2020-05-10 14:34:17

#pragma GCC optimize(3,"Ofast","inline")
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
ll n;
int k,m,z;
const int mo=998244353;
ll c[105][105],mi[105],g[210],ans[210],f[210][210],h[210][210];
void add()
{
	fo(i,1,m)g[i]=0;
	fo(i,1,m){
		fo(j,1,m)g[i]=(g[i]+ans[j]*f[j][i])%mo;
	}
	fo(i,1,m)ans[i]=g[i];
}
void mul()
{
	fo(i,1,m)fo(j,1,m)h[i][j]=0;
	fo(i,1,m)fo(k,1,m)fo(j,1,m)h[i][j]=(h[i][j]+f[i][k]*f[k][j])%mo;
	fo(i,1,m)fo(j,1,m)f[i][j]=h[i][j]%mo;
}
int main()
{
	//freopen("data.in","r",stdin);
	c[0][0]=1;
	fo(i,1,100){
		c[i][0]=1;
		fo(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
	}	
	scanf("%lld%d",&n,&k);
	mi[0]=1;
	fo(i,1,100)mi[i]=mi[i-1]*2%mo;
	fo(i,k+2,k+2+k)f[i][i-k-1]=1;
	f[k+2+k][k+2+k+1]=1;
	fo(i,k+2,k+2+k){
		z=i-k-2;
		fo(j,0,z)f[j+k+2][i]=c[z][j];
		fo(j,0,z)f[j+1][i]=c[z][j]*mi[z-j]%mo;
	}
	n--;
	fo(i,1,k+1)ans[i]=1;
	fo(i,k+2,k+2+k)ans[i]=mi[i-k-2];
	m=k+2+k+1;
	f[m][m]=1;
	ans[m]=1;
	while(n){
		if(n%2)add();
		mul();
		n/=2;
	}
	printf("%d\n",ans[m]);
}