Inv of Polynomials

AC一覧

Problem Statement
問題文

We consider polynomials of $\mathbb{Z}/998{,}244{,}353\mathbb{Z}$ 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.

$\mathbb{Z}/998{,}244{,}353\mathbb{Z}$ 係数の多項式 $f(x)=\sum_{i=0}^{N-1} a_ix^i ,g(x)=\sum_{i=0}^{M-1}b_ix^i$ が与えられます。 $\deg(h) < \deg(g)$ かつ $$f(x)h(x)\equiv1\pmod {g(x)}$$ を満たす$\mathbb{Z}/998{,}244{,}353\mathbb{Z}$ 係数の多項式 $h(x)=\sum_{i=0}^{T-1}c_ix^i$ を求めてください。 ただし $\deg(0)=-\infty$とします。 このような $h(x)$ は存在するならば一意に定まることが示せます。 $h(x)$ が存在しないときは$-1$を出力してください。

Constraints
制約

  • $1 \leq N \leq 50{,}000$
  • $1 \leq M \leq 50{,}000$
  • $0 \leq a_i < 998{,}244{,}353$
  • $0 \leq b_i < 998{,}244{,}353$
  • $a_{N-1} \neq 0$
  • $b_{M-1} \neq 0$

Input
入力

$N$ $M$
$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.

$h(x)$ が存在しないときは一行に $-1$ を出力してください。 $h(x)$ が存在するときは一行目に $T$ ($c_{T-1} \neq 0$) を出力してください。ただし $h(x)=0$ のときは $T=0$ としてください。 $h(x)$ が存在するときは二行目に $c_0,c_1,\ldots,c_{T-1}$ を空白区切りで出力してください。

$T$
$c_0$ $c_1$ $\ldots$ $c_{T - 1}$

Sample
サンプル

# 1

5 5
5 4 3 2 1
1 2 3 4 5
2
598946612 831870294

# 2

5 1
5 4 3 2 1
7
0

# 3

3 3
2 3 1
6 5 1
-1

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions