多项式求逆

【题目描述】

本题中我们考虑 $\mathbb{F}_{998244353}$ 上的多项式。

给定多项式 $f(x)=\sum_{i=0}^{N-1} a_ix^i$ 与 $g(x)=\sum_{i=0}^{M-1}b_ix^i$，求一个多项式 $h(x)=\sum_{i=0}^{T-1}c_ix^i$，满足

• $\deg(h) < \deg(g)$，且
• $f(x)h(x)\equiv1\pmod {g(x)}$。

注意本题中约定 $\deg(0)=-\infty$。可以证明，若 $h(x)$ 存在则唯一。若不存在，输出 $-1$。

【输入】

$N$ $M$
$a_0$ $a_1$ $\ldots$ $a_{N - 1}$
$b_0$ $b_1$ $\ldots$ $b_{M - 1}$

【输出】

若 $h(x)$ 不存在，输出 $-1$。

若 $h(x)$ 存在，第一行输出 $T$（$c_{T-1} \neq 0$）；当 $h(x)=0$ 时 $T = 0$。第二行输出 $c_0, c_1, \ldots, c_{T-1}$。

$T$
$c_0$ $c_1$ $\ldots$ $c_{T - 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

【输出样例2】

0

【输入样例3】

3 3
2 3 1
6 5 1

【输出样例3】

-1

【数据范围】

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

【来源】

Library Checker（yosupo06） inv_of_polynomials