【模板】多项式除法
题目描述
给定一个 $n$ 次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$ ,请求出多项式 $Q(x)$, $R(x)$,满足以下条件:
- $Q(x)$ 次数为 $n-m$,$R(x)$ 次数小于 $m$
- $F(x) = Q(x) * G(x) + R(x)$
所有的运算在模 $998244353$ 意义下进行。
输入输出格式
输入格式
第一行两个整数 $n$,$m$,意义如上。
第二行 $n+1$ 个整数,从低到高表示 $F(x)$ 的各个系数。
第三行 $m+1$ 个整数,从低到高表示 $G(x)$ 的各个系数。
输出格式
第一行 $n-m+1$ 个整数,从低到高表示 $Q(x)$ 的各个系数。
第二行 $m$ 个整数,从低到高表示 $R(x)$ 的各个系数。
如果 $R(x)$ 不足 $m-1$ 次,多余的项系数补 $0$。
输入输出样例
输入样例 #1
5 1
1 9 2 6 0 8
1 7
输出样例 #1
237340659 335104102 649004347 448191342 855638018
760903695
说明
对于所有数据,$1 \le m < n \le 10^5$,给出的系数均属于 $[0, 998244353) \cap \mathbb{Z}$。