#P6800. 【模板】Chirp Z-Transform

【模板】Chirp Z-Transform

题目描述

给定一个 nn 项多项式 P(x)P(x) 以及 c,mc, m,请计算 P(c0),P(c1),,P(cm1)P(c^0),P(c^1),\dots,P(c^{m-1})。所有答案都对 998244353998244353 取模。

输入格式

第一行三个正整数 n,c,mn,c,m
第二行 nn 个非负整数 a0,a1,,an1a_0,a_1,\dots,a_{n-1},由低到高表示 P(x)P(x) 的系数。

输出格式

一行 mm 个正整数,第 ii 个数表示 P(ci1)P(c^{i-1})

3 3 3
3 3 3
9 39 273

提示

对于 100%100\% 的数据,1n,m106,0c,ai<9982443531\le n,m\le 10^6,0\le c,a_i<998244353.