多项式除法

【题目描述】

给定多项式 $f(x) = \sum _ {i = 0} ^ {N - 1} f _ i x^i \in \mathbb{F} _ {998244353}[x]$ 和 $g(x)=\sum _ {i=0}^{M-1}g_ix^i\in \mathbb{F}_{998244353}[x]$。计算多项式 $q(x)$ 和 $r(x)$，满足

• $f(x) = q(x)g(x) + r(x)$；
• $\deg(r) \lt \deg(g)$。

【输入】

输入格式如下：

$N\ M$
$f_0\ f_1\ \ldots\ f_{N - 1}$
$g_0\ g_1\ \ldots\ g_{M - 1}$

【输出】

第一行输出 $u=\deg(q)+1$ 和 $v=\deg(r)+1$。如果 $q(x)=0$，则令 $u=0$。（对于 $r(x)$ 也同样处理。）

第二行输出多项式 $q(x)$ 的系数，第三行输出多项式 $r(x)$ 的系数。

输出格式如下：

$u\ v$
$q_0\ q_1\ \ldots\ q_{u-1}$
$r_0\ r_1\ \ldots\ r_{v-1}$

【输入样例】

7 3
0 0 0 0 0 0 1
998244352 998244352 1

【输出样例】

5 2
5 3 2 1 1
5 8

【输入样例2】

4 5
1 2 3 4
5 6 7 8 9

【输出样例2】

0 4

1 2 3 4

【输入样例3】

1 1
1
1

【输出样例3】

1 0
1

【输入样例4】

4 3
1 2 3 4
5 6 7

【输出样例4】

2 2
916755018 427819009
407446676 346329673

【数据范围】

• $1 \leq N \leq 500000$
• $1 \leq M \leq 500000$
• $0 \leq f_i < 998244353$
• $0 \leq g_i < 998244353$
• $f_{N-1} \neq 0$
• $g_{M-1} \neq 0$

【来源】

Library Checker（yosupo06） division_of_polynomials