卷积（Convolution (Mod $2^{64}$)）

问题描述

给定两个整数序列 $a_0, a_1, \dots, a_{N-1}$ 和 $b_0, b_1, \dots, b_{M-1}$，计算它们的离散卷积序列

$$c_0, c_1, \dots, c_{(N-1)+(M-1)},$$

其中：

$$c_k = \sum_{\substack{i+j = k \\ 0 \le i < N \\ 0 \le j < M}} a_i b_j \bmod 2^{64}.$$

注：模 $2^{64}$ 表示结果取低 64 位无符号整数（即自然溢出），等价于在 $\mathbb{Z}/2^{64}\mathbb{Z}$ 中运算。

约束条件

• $1 \leq N, M \leq 2^{19}$
• $0 \leq a_i, b_i < 2^{64}$

输入格式

$N\ M$
$a_0\ a_1\ \cdots\ a_{N-1}$
$b_0\ b_1\ \cdots\ b_{M-1}$

输出格式

$c_0\ c_1\ \cdots\ c_{N+M-2}$

4 5
1 2 3 4
5 6 7 8 9

5 16 34 60 70 70 59 36

1 1
10000000000000000000
10000000000000000000

687399551400673280