102453: [AtCoder]ABC245 D - Polynomial division

Problem Statement

We have a polynomial of degree $N$, $A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots +A_1x+A_0$,
and another of degree $M$, $B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots +B_1x+B_0$.
Here, each coefficient of $A(x)$ and $B(x)$ is an integer whose absolute value is at most $100$, and the leading coefficients are not $0$.

Also, let the product of them be $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$.

Given $A_0,A_1,\ldots, A_N$ and $C_0,C_1,\ldots, C_{N+M}$, find $B_0,B_1,\ldots, B_M$.
Here, the given inputs guarantee that there is a unique sequence $B_0, B_1, \ldots, B_M$ that satisfies the given conditions.

Constraints

• $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$
• There is a unique sequence $B_0, B_1, \ldots, B_M$ that satisfies the conditions given in the statement.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$ $A_N$
$C_0$ $C_1$ $\ldots$ $C_{N+M-1}$ $C_{N+M}$

Output

Print the $M+1$ integers $B_0,B_1,\ldots, B_M$ in one line, with spaces in between.

Sample Input 1

1 2
2 1
12 14 8 2

Sample Output 1

6 4 2

For $A(x)=x+2$ and $B(x)=2x^2+4x+6$, we have $C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12$, so $B(x)=2x^2+4x+6$ satisfies the given conditions. Thus, $B_0=6$, $B_1=4$, $B_2=2$ should be printed in this order, with spaces in between.

Sample Input 2

1 1
100 1
10000 0 -1

Sample Output 2

100 -1

We have $A(x)=x+100$, $C(x)=-x^2+10000$, for which $B(x)=-x+100$ satisfies the given conditions. Thus, $100$, $-1$ should be printed in this order, with spaces in between.

问题描述

我们有一个次数为$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$。

约束

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

输入

输入从标准输入按以下格式给出：

$N$ $M$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$ $A_N$
$C_0$ $C_1$ $\ldots$ $C_{N+M-1}$ $C_{N+M}$

输出

在一行中打印$B_0,B_1,\ldots, B_M$，中间用空格隔开。

样例输入1

1 2
2 1
12 14 8 2

样例输出1

6 4 2

对于$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$，中间用空格隔开。

样例输入2

1 1
100 1
10000 0 -1

样例输出2

100 -1

我们有$A(x)=x+100$，$C(x)=-x^2+10000$，对于其中$B(x)=-x+100$满足给定条件。因此，应该按顺序打印$100$，$-1$，中间用空格隔开。