背景

本题来自 https://github.com/yosupo06/library-checker-problems。

题目描述

给定整数 $N,a,r$ 以及整数序列 $y_0,y_1,\dots,y_{N-1}$。保证对于 $0\leq i<j\leq N-1$，有 $ar^i\not\equiv ar^j\pmod{998244353}$。

求出一个多项式 $f(x)=\sum_{i=0}^{N-1}c_ix^i\in \mathbb{Z}[x]$，使得对于每个 $i$，均满足 $f(ar^i)\equiv y_i\pmod{998244353}$。

同时，必须满足 $0\leq c_i<998244353$。

输入格式

$N\ a\ r$
$y_0\ y_1\ \dots\ y_{N-1}$

输出格式

$c_0\ c_1\ \dots\ c_{N-1}$

4 2 10
17 1241 120401 12004001

1 2 3 0

1 0 0
100

100

提示

• $0\leq N\leq 2^{19}$
• $0\leq a < 998244353$
• $0\leq r < 998244353$
• $0\leq y_i < 998244353$
• $ar^i\not\equiv ar^j \pmod{998244353}\,(0\leq i<j\leq N-1)$