#166. 拉格朗日插值 2

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cutekibry

题目描述

这是一道模板题。

给出次数不超过 n 的函数 f(x) 在点 0, 1, \ldots, n 上的取值 f(0), f(1), \ldots, f(n) ,以及一个整数 m ,请求出 f(m), f(m + 1), \ldots, f(m + n) 的值。

可以证明,该函数必定存在且唯一。

由于答案可能很大,你只需要输出答案 \bmod 998244353 的值。

输入格式

第一行,两个整数 n, m ,表示函数次数不超过 n ,以及计算要求。

第二行, n + 1 个整数 f(0), f(1), \ldots, f(n) ,表示函数 f(x) 在点 0, 1, \ldots, n 上的取值。

输出格式

只有一行, n + 1 个整数 f(m), f(m + 1), \ldots, f(m + n) ,表示答案。

由于答案可能很大,你只需要输出答案 \bmod 998244353 的值。

样例

样例输入 1

2 4
5 7 15

样例输出 1

49 75 107

样例解释 1

解得函数 f(x) = 3x^2 - x + 5 ,因此 f(4) = 49, f(5) = 75, f(6) = 107

样例输入 2

4 10
5 3 29 83 141

样例输出 2

998240558 998237956 998234302 998229356 998222854

样例解释 2

解得函数 f(x) = -x^4 + 6x^3 + 3x^2 - 10x + 5 ,因此 f(10) = -3795, f(11) = -6397, f(12) = -10051, f(13) = -14997, f(14) = -21499

数据范围与提示

对于 100\% 的数据, 1 \leq n \leq 100000, 1 \leq f(i) < 998244353, n < m \leq 10^8

数据有一定梯度。