打表经典题。

手算一下：

n	1	2	3	4	5	6
ans	1	1	2	3	7	16

oeis上查一下，表在这里

这时候输入表，直接高精取余即可。

打表程序：

#include<iostream>
#include<cstring>
using namespace std;
long long check(string a){//对998244353取余
	long long ans=0;
	for(int i=0;i<a.length();i++){
		ans=(ans*10+a[i]-'0')%998244353;
	}
	return ans;
} 
int main(){
	freopen("smal.in","r",stdin);//一定要加，不加复制不了表
	freopen("smal.out","w",stdout);
	long long ans;
	int bh;
	string s;
	for(int i=0;i<50;i++){
		cin>>bh>>s;
		ans=check(s);
		cout<<ans<<",";//输出表
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Code:

#include<iostream>
using namespace std;
int a[51]={0,1,1,2,3,7,16,54,243,2038,33120,1182004,87723296,907260828,445874017,131059413,750854059,85710140,46269468,106575268,569924828,477980796,853121491,916490672,848722293,179336057,577163661,709912061,916083428,988859367,286999618,29547862,713350279,194424628,553076032,609634772,876525030,182311698,148716617,346128108,650982654,373128192,361260409,524419271,834718796,514750301,478609700,386216865,881562716,715225681,602577017};
int main(){
	int n;
	cin>>n;
	cout<<a[n];
	return 0;
}