AT_abc245_d.[ABC245D] Polynomial division

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

现在有 NN 次多项式 A(x)=ANxN+AN−1xN−1+⋯ +A1x+A0A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots\ +A_1x+A_0 和 MM 次多项式 B(x)=BMxM+BM−1xM−1+⋯ +B1x+B0B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots\ +B_1x+B_0。

其中,A(x)、B(x)A(x)、B(x) 中的每个系数都是绝对值小于等于 100100 的整数,并且最高的下一个系数不是 00。

定义它们的积为 C(x)=A(x)B(x)=CN+MxN+M+CN+M−1xN+M−1+⋯ +C1x+C0C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\cdots\ +C_1x+C_0。

已知 A0,A1,…, ANA_0,A_1,\ldots,\ A_N 和 C0,C1,…, CN+MC_0,C_1,\ldots,\ C_{N+M},请求出 B0,B1,…, BMB_0,B_1,\ldots,\ B_M。

输入保证只有一种 B0,B1,…, BMB_0,B_1,\ldots,\ B_M。

输入格式

第一行输入 N,MN,M;

第二行输入 A0,A1,…,AN−1A_0,A_1,\ldots,A_{N-1};

第三行输入 C0,C1,…,CN+MC_0,C_1,\ldots,C_{N+M}。

输出格式

输出 M+1M+1 个整数 B0,B1,…, BMB_0,B_1,\ldots,\ B_M。

输入输出样例

  • 输入#1

    1 2
    2 1
    12 14 8 2

    输出#1

    6 4 2
  • 输入#2

    1 1
    100 1
    10000 0 -1

    输出#2

    100 -1

说明/提示

  • $ 1\leq N<100 $

  • $ 1\leq M<100 $

  • $ |A_i|\leq100 $

  • $ |C_i|\leq10^6 $

  • $ A_N\neq0 $

  • $ C_{N+M}\neq0 $

  • 满足条件的 B0,B1,…, BMB_0,B_1,\ldots,\ B_M 只有一个

输入解题思路,AI测评打分。不知道怎么写?

首页