#41. 多项式乘法

    ID: 41 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>模板数学多项式 / 形式幂级数DFT(含 NTT)及FFT

多项式乘法

题目描述

这是一道模板题。

输入两个多项式,输出这两个多项式的乘积。

输入格式

第一行两个整数 n n m m ,分别表示两个多项式的次数。

第二行 n+1 n + 1 个整数,分别表示第一个多项式的 0 0 n n 次项前的系数。

第三行 m+1 m + 1 个整数,分别表示第二个多项式的 0 0 m m 次项前的系数。

输出格式

一行 n+m+1 n + m + 1 个整数,分别表示乘起来后的多项式的 0 0 n+m n + m 次项前的系数。

样例

1 2
1 2
1 2 1
1 4 5 2

数据范围与提示

0n,m105 0 \leq n, m \leq 10 ^ 5 ,保证输入中的系数大于等于 0 0 且小于等于 9 9