luogu#P5667. 拉格朗日插值2

    ID: 9689 远端评测题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>快速数论变换 NTT数论数学快速傅里叶变换,FFT

拉格朗日插值2

题目描述

给定一个不超过 nn 次的多项式的 n+1n+1 个点值 f(0),f(1)f(n)f(0),f(1) \dots f(n),和一个正整数 mm,求 f(m),f(m+1)f(m+n)f(m),f(m+1) \dots f(m+n)

答案对 998244353998244353 取模。

输入格式

第一行两个正整数 n,mn,m,意义如题目描述。
第二行 n+1n+1 个整数,表示 f(0),f(1)f(n)f(0),f(1) \dots f(n)

输出格式

输出一行 n+1n+1 个整数,表示 f(m),f(m+1)f(m+n)f(m),f(m+1) \dots f(m+n)

5 6
1 1 4 5 1 4
54 232 673 1579 3232 6007

提示

【数据范围】
对于 100%100\% 的数据:
1n1600001 \le n \le 160000n<m108n < m \le 10^80f(i)<9982443530 \le f(i) < 998244353