Azuki loves coloring
题目描述
NEKOPARA Vol.3 发售之后,在新作中不是主角的 Azuki 终于可以休息了。为了打发时间,她开始给一个由 $n$ 个格子组成的序列涂色,每个格子可以涂黑白灰三种颜色之一。为了美观,Azuki 希望序列中没有两个黑色的格子相邻,也没有两个白色的格子相邻。这样的序列有很多,Azuki 定义每个序列的权值是其中一个黑色格子和一个白色格子相邻的情况的出现次数,如序列“灰黑白黑”的权值为 $2$。Azuki 想知道,对于满足 $0\le i\le k$ 的每一个 $i$,长度为 $n$ 且权值为 $i$ 的序列有多少种。由于答案很大,因此她只需要知道答案 $\text{mod }998244353$ 的值就可以了。Azuki 答应你,如果你解决了这个问题,她就可以给你做~~美味的蛋糕吃~~。
输入输出格式
输入格式
一行两个正整数 $n,k$。
输出格式
一行 $k+1$ 个正整数,分别代表权值为 $0,1,\dots,k$ 的序列的个数 $\text{mod }998244353$ 的值。
输入输出样例
输入样例 #1
3 3
输出样例 #1
11 4 2 0
输入样例 #2
20 10
输出样例 #2
1398101 4582670 8103780 10126770 9931780 8075094 5618340 3422330 1841460 893790 383524
说明
对于 $30\%$ 的测试点,$n,k\le 100$。
对于 $50\%$ 的测试点,$n,k\le 5000$,时限 $1s$。其余测试点时限 $5s$。
对于 $70\%$ 的测试点,$n,k\le 60000$。
对于 $100\%$ 的测试点,$n\le 10^{18},k\le 100000$。