11318: [yosupo] Polynomial - Polynomial Interpolation (Geometric Sequence)
[Creator : ]
Description
Given integers $N, a, r$ and integer sequence $y_0, y_1, ..., 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.
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.
Input
$N$ $a$ $r$
$y_0$ $y_1$ ... $y_{N-1}$
$y_0$ $y_1$ ... $y_{N-1}$
Output
$c_0$ $c_1$ ... $c_{N -1}$
Constraints
- $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)$
- $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)$
Sample 1 Input
4 2 10
17 1241 120401 12004001
Sample 1 Output
1 2 3 0
Sample 2 Input
1 0 0
100
Sample 2 Output
100