题目背景

This problem comes from the repository https://github.com/yosupo06/library-checker-problems.

题目描述

Given integers $N,a,r$ and integer sequence $y_0,y_1,\dots,y_{N-1}$. It is guaranteed that $ar^i\not\equiv ar^j \pmod{998244353}$ for $0\leq i < j\leq N-1$.

Calculate a polynomial $f(x)=\sum_{i=0}^{N-1} c_i x^i \in \mathbb{Z}[x]$ s.t. $f(ar^i)\equiv y_i \pmod{998244353}$ is satisfied for each $i$.

Also, $0\leq c_i< 998244353$ must be satisfied.

输入格式

$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)$