← 返回题目列表

AtCoder · abc245_d

G. 多项式除法

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个次数多项式 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}

输出

打印 M+1 整数 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 应按此顺序打印,中间有空格。