Convolution

AC一覧

Problem Statement
問題文

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_i = \sum_{j = 0}^i a_j b_{i - j} \bmod 998{,}244{,}353$$

整数列 $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 998{,}244{,}353$$

です

Constraints
制約

Input
入力

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

Output
出力

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

Sample
サンプル

# 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
871938225

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions