Polynomial division

题目描述

我们有一个次数为 $N$ 的多项式 $A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots +A_1x+A_0$,
以及另一个次数为 $M$ 的多项式 $B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots +B_1x+B_0$.
这里，$A(x)$ 和 $B(x)$ 的每个系数都是绝对值不超过 $100$ 的整数，并且首项系数不为 $0$。 另外，令它们的乘积为 $C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\cdots +C_1x+C_0$。 给定 $A_0,A_1,\ldots, A_N$ 和 $C_0,C_1,\ldots, C_{N+M}$，求出 $B_0,B_1,\ldots, B_M$.
在这里，给定的输入保证存在唯一满足条件的序列 $B_0, B_1, \ldots, B_M$。

输入格式

输入采用标准输入，格式如下： $N$ $M$ $A_0$ $A_1$ $\ldots$ $A_{N-1}$ $A_N$ $C_0$ $C_1$ $\ldots$ $C_{N+M-1}$ $C_{N+M}$

输出格式

在一行中输出 $M+1$ 个整数 $B_0,B_1,\ldots, B_M$，中间用空格分隔。

1 2
2 1
12 14 8 2

6 4 2

1 1
100 1
10000 0 -1

100 -1

提示

1 \leq N < 100 1 \leq M < 100 $|A_i| \leq 100$ $|C_i| \leq 10^6$ $A_N \neq 0$ $C_{N+M} \neq 0$ 存在唯一的序列 $B_0, B_1, \ldots, B_M$ 满足题目中给出的条件。对于 $A(x)=x+2$ 和 $B(x)=2x^2+4x+6$，有 $C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12$，因此 $B(x)=2x^2+4x+6$ 满足给定条件。故应按此顺序输出 $B_0=6$、$B_1=4$、$B_2=2$，中间用空格分隔。
我们有 $A(x)=x+100$，$C(x)=-x^2+10000$，其对应的 $B(x)=-x+100$ 满足给定条件。 因此应按此顺序输出 $100$、$-1$，中间用空格分隔。

标签: AtCoder|abc245D

来源

AtCoder|abc245D