QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 618. 多项式乘法

统计

题目描述

给定 $n$ 次多项式 $A(z)=\sum^n_{i=0} a_iz^i$ 与 $m$ 次多项式 $B(z)=\sum^n_{i=0} b_iz^i$,求它们的乘积 $C(z) = \sum^{n+m}_{i=0} c_iz^i$。

输入格式

输入的第一行包含两个整数 $n,m$。

接下来一行,包含 $n + 1$ 个整数 $a_0,a_1,\cdots,a_n$。

接下来一行,包含 $m + 1$ 个整数 $b_0,b_1,\cdots,b_m$。

输出格式

输出一行 $n+m+1$ 个整数,表示 $c_0,c_1,\cdots,c_{n+m}$。

样例数据

样例输入

2 3
1 2 3
3 4 5 6

样例输出

3 10 22 28 27 18

子任务

对于所有数据,$1 \leq n,m \leq 10^6$。

测试点 $n,m\leq$
$1$ $100$
$2$ $5 \times 10^3$
$3$ $3 \times 10^4$
$4$ $10^5$
$5$ $10^6$