3410. Knight的多项式除法

【题目描述】

给定一个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。

【样例输入】

5 1

1 9 2 6 0 8

1 7

【样例输出】

237340659 335104102 649004347 448191342 855638018

760903695

【提示】

对于所有数据，$1 \leq m < n \leq 10^5$ ,给出的系数均属于$[0,998244353) \cap \mathbb{Z}$

【来源】

luogu4512