Oh No! You need to sign in or sign up before continuing.
3432 . [模板題] Inv of Formal Power Series
TopCoder
Tags
Description
You are given a formal power series $f(x) = \sum_ {i=0}^ {N-1} a_ i x^ i \in \mathbb{F}_ {998244353}[[x]]$ with $a_ 0 \ne 0$.
Calculate the first $N$ terms of $\frac{1}{f(x)} = \sum_ {i=0}^ {\infty} b_ i x^ i$.
In other words, find $g(x) = \sum_ {i=0}^ {N-1} b_ i x^ i \in \mathbb{F}_ {998244353}[[x]]$ such that
$$f(x) g(x) \equiv 1 \pmod{x^ N}.$$
Input Format
$N$
$a_ 0$ $a_ 1$ $\cdots$ $a_ {N - 1}$
Output Format
$b_ 0$ $b_ 1$ $\cdots$ $b_ {N - 1}$
Sample Input 1
5 5 4 3 2 1
Sample Output 1
598946612 718735934 862483121 635682004 163871793
Hints
- $1 \leq N \leq 5 \times 10^ {5}$
- $0 \leq a_ i < 998244353$
- $a_ 0 \neq 0$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|