← 返回题目列表

AtCoder · practice2_f

F. 卷积

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

分数: 100 点

问题陈述

给你两个整数数组 a_0, a_1, ..., a_{N - 1} 和 b_0, b_1, ..., b_{M - 1}。计算数组 c_0, c_1, ..., c_{(N - 1) + (M - 1)},定义为 c_i = \sum_{j = 0}^i a_j b_{i - j} \bmod 998244353.

约束

  • 1 \leq N, M \leq 524288
  • 0 \leq a_i, b_i < 998244353
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{M-1}

输出

按以下格式打印答案:

c_0 c_1 ... c_{(N - 1) + (M - 1)}

示例输入 1

4 5
1 2 3 4
5 6 7 8 9

示例输出 1

5 16 34 60 70 70 59 36

示例输入 2

1 1
10000000
10000000

示例输出 2

871938225