#P7390. [2019雅礼集训]Between Boundaries

    ID: 7404 传统题 4000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学生成函数转化线性代数与代数线性递推多项式与生成函数截断幂级数NTT多项式求逆多项式平方根多项式对数多项式指数多项式牛顿迭代导数积分转化生成函数求系数CF2700

[2019雅礼集训]Between Boundaries

Between Boundaries

题目描述

原题示意图

小BB和小SS分别是两个不同帮派的大哥。他们都想要吞并对方,但是因为实力相近所以都不得成功。

这天,小SS 从国家队论文集古代魔法书中找到了一种船心膜法。这种膜法可以召唤恶魔,用来大规模的拆迁破坏行动。小SS自然是立即使用了这种膜法。

然而,在 Sunway 的帮助下,小BB 召集了 1 mol 小弟站在城墙上来防御。城墙长为nn ,每一格城墙都会站着一个小弟,每个小弟手上都会拿着红黄蓝 33 种颜色之一的膜法石。

根据 Sunway 的运算结果,相邻的两个都是红色的或者都是黄色的膜法石会产生能量波动,这是绝对不允许的。与此同时,相邻的红色和黄色膜法石会消耗小BB 一点法力值,然后增加一点护盾。

现在,小BB想问你,分别对于恰好消耗 j=0,1,…,mj=0,1,\ldots,m 点法力值的防御措施,一共有多少种不同的排列方式? 两种方式视为不同当且仅当存在一个位置,这个位置的小弟在两种方案中拿着不同颜色的膜法石。答案对 998244353998244353 取模。

输入格式

一行两个整数 n,mn,m,表示城墙的长度和法力值上限。

输出格式

一行输出 m+1m+1 个整数,第 j+1j+1 个整数表示恰好消耗 jj 点法力值的合法排列数量,对 998244353998244353 取模,0≤j≤m0\le j\le m。

样例输入

3 4

样例输出

11 4 2 0 0

样例解释

举例来说,消耗 11 点法力值的方案有红黄蓝,黄红蓝,蓝红黄,蓝黄红四种。

数据范围

所有数据满足 n≤1018n\le10^{18},m≤105m\le10^5。

子任务 分值 附加限制
1 5 n,m≤100n,m\le100
2 15 n,m≤5000n,m\le5000
3 m≤1000m\le1000
4 25 m≤5000m\le5000
5 30 m≤104m\le10^4
6 10 m≤105m\le10^5

后记

小BB成功地抵抗住了小SS的袭击,带着他 11mol 女朋友去看电影去了。