9006: [yosupo] Convolution - Convolution (Mod $2^{64}$)
[Creator : ]
Description
Given integer sequences $a_0, a_1, ..., a_{N - 1}$ and $b_0, b_1, ..., b_{M - 1}$. Calculate an integer sequence $c_0, c_1, ..., c_{(N - 1) + (M - 1)}$ as follows:
$c_k = \sum_{i+j=k} a_ib_j \bmod 2^{64}$
$c_k = \sum_{i+j=k} a_ib_j \bmod 2^{64}$
Input
$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$
Output
$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$
Constraints
$1 \leq N, M \leq 2^{19}$
$0 \leq a_i, b_i < 2^{64}$
$0 \leq a_i, b_i < 2^{64}$
Sample 1 Input
4 5
1 2 3 4
5 6 7 8 9
Sample 1 Output
5 16 34 60 70 70 59 36
Sample 2 Input
1 1
10000000000000000000
10000000000000000000
Sample 2 Output
687399551400673280