컨볼루션

시간 제한3초메모리 제한512 MB

요약

길이가 n+1인 수열 a와 b가 주어질 때, 모든 k에 대해 C(k,i)·a_i·b_(k-i)의 합을 2^32로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 분할 정복, 조합론, 정수론
정답자: 아직 제출이 없습니다

문제

두 수열 $a_0, a_1, \ldots, a_n$ 과 $b_0, b_1, \ldots, b_n$ 이 주어진다. 다음 식으로 새로운 수열 $c_0, c_1, \ldots, c_n$ 을 구하시오.

$c_k = \left(\sum_{i = 0}^k {k \choose i} a_i b_{k-i}\right) \bmod 2^{32}$

여기서 ${k \choose i} = \frac{k!}{i! (k - i)!}$ 은 이항 계수이다.

입력

첫째 줄에 정수 $n$ 이 주어진다 ( $1 \leq n \leq 2 \cdot 10^5$ ). 둘째 줄에 $n + 1$ 개의 정수 $a_0, a_1, \ldots, a_n$ 이 주어진다 ( $0 \leq a_i < 2^{32}$ ). 셋째 줄에 $n + 1$ 개의 정수 $b_0, b_1, \ldots, b_n$ 이 주어진다 ( $0 \leq b_i < 2^{32}$ ).

출력

$c_0, c_1, \ldots, c_n$ 을 한 줄에 출력한다.

예제1

예제 1

입력

5
0 1 2 3 4 5
6 7 8 9 10 11

예상 출력

0 6 26 84 240 640