P14993 【模板】Inverse Chirp Z-Transform

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

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