(追記) (追記ここまで)

33966번 - 격자 경로의 가중치

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	1024 MB	88	27	27	54.000%

문제

$K \leq t \leq N$인 모든 정수 $t$에 대하여, 좌표평면 위의 격자점 $(0,0)$에서 출발해 다음 규칙에 따른 행동을 원하는 횟수만큼 시행해 격자점 $(t,t)$에 도착하는 경로를 생각해 보자.

$x \gt y$인 점 $(x,y)$에서는 $(x+1,y)$ 또는 $(x,y+1)$로 이동할 수 있다.
$x \leq y$인 점 $(x,y)$에서는 $(x+K,y+K-1)$로 이동할 수 있다.

좌표평면 위의 직선 $y=x$ 상에 있는 격자점 $(i,i)$는 가중치 $a_i$를 가진다. 한 경로의 가중치는 경로에 포함된 직선 $y=x$ 상에 있는 모든 격자점의 가중치의 곱으로 정의한다.

점 $(0,0)$에서 출발해 점 $(t,t)$에 도착하는 서로 다른 경로의 가중치의 합을 구하여라. 경로에 포함된 점의 집합이 일치하지 않으면 다른 격자 경로이다.

입력

첫째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200,000円)$

둘째 줄에 $N+1$개의 정수 $a_0,ドル $a_1,ドル $\cdots,ドル $a_{N}$이 공백으로 구분되어 주어진다. $(0 \leq a_i \lt 998,244円,353円)$

출력

$K \leq t \leq N$인 모든 정수 $t$에 대하여, 첫째 줄에 점 $(0,0)$에서 출발해 행동을 원하는 횟수만큼 시행해 점 $(t,t)$에 도착하는 서로 다른 격자 경로의 가중치의 합을 998ドル,244円,353円$로 나눈 나머지를 공백으로 구분하여 출력한다.

제한

예제 입력 1

4 2
1 2 3 4 5

예제 출력 1

3 4 25

$(0,0)$에서 $(2,2)$까지 가는 경로는 $(0,0) \rightarrow (2,1) \rightarrow (2,2)$뿐이며, 경로의 가중치는 1ドル \times 3=3$이다.

$(0,0)$에서 $(3,3)$까지 가는 경로는 $(0,0) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3)$뿐이며, 경로의 가중치는 1ドル \times 4=4$이다.

$(0,0)$에서 $(4,4)$까지 가는 경로는 $(0,0) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (4,3) \rightarrow (4,4),ドル $(0,0) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (4,2) \rightarrow (4,3) \rightarrow (4,4),ドル $(0,0) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (4,1) \rightarrow (4,2) \rightarrow (4,3) \rightarrow (4,4)$가 있으며, 경로의 가중치는 각각 1ドル \times 3 \times 5 = 15,ドル 1ドル \times 5 = 5,ドル 1ドル \times 5 = 5$이다.