【题目描述】
给定整数序列 a0,a1,...,aN−1 和 b0,b1,...,bM−1。请按照如下方式计算整数序列 c0,c1,...,c(N−1)+(M−1):
ck=i+j=k∑aibjmod998244353【输入】
文本
$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)}$
【输入样例】
文本
4 5
1 2 3 4
5 6 7 8 9
【输出样例】
文本
5 16 34 60 70 70 59 36
【输入样例2】
文本
1 1
10000000
10000000
【输出样例2】
【数据范围】
- 1≤N,M≤16777216
- 0≤ai,bi<998244353
【来源】
Library Checker(yosupo06) convolution_mod_large