分数: 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