FFT를 사용하라

시간 제한10초메모리 제한1024 MB

요약

각 k에 대해 C_i에 j=1부터 k까지 (A_i+B_j)의 곱을 곱하고, 이를 모든 i에 걸쳐 더한 값을 998244353으로 나눈 나머지를 구합니다.

문제

길이가 각각 $N$ 인 정수 수열 $A$ , $B$ , $C$ 가 주어진다. 각 $k=1,2,\ldots,N$ 에 대해 아래 값을 998244353으로 나눈 나머지를 구하라.

$\sum_{1 \leq i \leq N} \left( C_i \times \prod_{1 \leq j \leq k} (A_i+B_j) \right)$

첫 줄에 정수 $N$ 이 주어진다 ( $1 \leq N \leq 250000$ ).

둘째 줄에 $N$ 개의 정수 $A_1, A_2, \ldots, A_N$ 이 주어진다 ( $0 \leq A_i < 998244353$ ).

셋째 줄에 $N$ 개의 정수 $B_1, B_2, \ldots, B_N$ 이 주어진다 ( $0 \leq B_i < 998244353$ ).

넷째 줄에 $N$ 개의 정수 $C_1, C_2, \ldots, C_N$ 이 주어진다 ( $0 \leq C_i < 998244353$ ).

각 $k=1,2,\ldots,N$ 에 대한 답을 출력한다.