11322: [yosupo] Polynomial - Inv of Polynomials
[Creator : ]
Description
We consider polynomials over $\mathbb{F}_{998244353}$ in this problem.
Given polynomials $f(x)=\sum_{i=0}^{N-1} a_ix^i$ and $g(x)=\sum_{i=0}^{M-1}b_ix^i$.
Calculate a polynomial $h(x)=\sum_{i=0}^{T-1}c_ix^i$ s.t.
- $\deg(h) < \deg(g)$ and
- $f(x)h(x)\equiv1\pmod {g(x)}$
is satisfied.
We note that $\deg(0)=-\infty$ in this problem.
We can prove $h(x)$ is unique if it exists.
Print $-1$ if it doesn't exist.
Given polynomials $f(x)=\sum_{i=0}^{N-1} a_ix^i$ and $g(x)=\sum_{i=0}^{M-1}b_ix^i$.
Calculate a polynomial $h(x)=\sum_{i=0}^{T-1}c_ix^i$ s.t.
- $\deg(h) < \deg(g)$ and
- $f(x)h(x)\equiv1\pmod {g(x)}$
is satisfied.
We note that $\deg(0)=-\infty$ in this problem.
We can prove $h(x)$ is unique if it exists.
Print $-1$ if it doesn't exist.
Input
$N$ $M$
$a_0$ $a_1$ $\ldots$ $a_{N - 1}$
$b_0$ $b_1$ $\ldots$ $b_{M - 1}$
$a_0$ $a_1$ $\ldots$ $a_{N - 1}$
$b_0$ $b_1$ $\ldots$ $b_{M - 1}$
Output
If $h(x)$ doesn't exist, print $-1$.
If $h(x)$ exists, print $T$ ($c_{T-1} \neq 0$) in first line, or $T = 0$ when $h(x)=0$.
Print $c_0, c_1, \ldots, c_{T-1}$ in next line.
$T$
$c_0$ $c_1$ $\ldots$ $c_{T - 1}$
If $h(x)$ exists, print $T$ ($c_{T-1} \neq 0$) in first line, or $T = 0$ when $h(x)=0$.
Print $c_0, c_1, \ldots, c_{T-1}$ in next line.
$T$
$c_0$ $c_1$ $\ldots$ $c_{T - 1}$
Constraints
- $1 \leq N \leq 50000$
- $1 \leq M \leq 50000$
- $0 \leq a_i < 998244353$
- $0 \leq b_i < 998244353$
- $a_{N-1} \neq 0$
- $b_{M-1} \neq 0$
- $1 \leq M \leq 50000$
- $0 \leq a_i < 998244353$
- $0 \leq b_i < 998244353$
- $a_{N-1} \neq 0$
- $b_{M-1} \neq 0$
Sample 1 Input
5 5
5 4 3 2 1
1 2 3 4 5
Sample 1 Output
2
598946612 831870294
Sample 2 Input
5 1
5 4 3 2 1
7
Sample 2 Output
0
Sample 3 Input
3 3
2 3 1
6 5 1
Sample 3 Output
-1