#91. 拉格朗日插值 2

拉格朗日插值 2

当前没有测试数据。

题目描述

这是一道模板题。

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

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

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

输入格式

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

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

输出格式

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

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

样例 1

2 4
5 7 15
49 75 107

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

4 10
5 3 29 83 141
998240558 998237956 998234302 998229356 998222854

解得函数 f(x)=x4+6x3+3x210x+5f(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%100\% 的数据,$1 \leq n \leq 100000, 1 \leq f(i) < 998244353, n < m \leq 10^8$。

数据有一定梯度。