DP宝塔
1030
2023.01.13
发布于 未知归属地

宝塔
巍巍宝塔高n层,今天不计算有几盏灯。从地下一层到顶层把宝塔的每一层依次编号为0~n,除了第k层,每一层都有一个传送门,传送门最多可以向上传送三层。例如,sasha在高为3层宝塔的地下一层,刚好这一层有一个传送门,那么sasha可以借助这个传送门到达宝塔的第1层,或者第2层,或者第3层。现在sasha在地下一层,试问:对于每个给定的n和k,sasha有多少种方式到达塔的顶层?

输入格式:
多组输入

对于每组输入在一行中给出 2 个整数 n 和 k。

数据保证有 1≤k<n≤10
​6
​​ 。

输出格式:
对于每组输入,输出一行,代表对应输入的到达塔顶层的方案数。

结果对998244353 取余后输出。

输入样例:
在这里给出一组输入。例如:

4 3
输出样例:
在这里给出相应的输出。例如:

3

评论 (7)