RiseOJ – 자기 자신을 부르는 수열

설명

길이가 $$N$$ 인 띠를 색칠하려고 한다. 우선 띠를 길이가 $$1$$ 이상인 연속한 토막들로 빈틈없이 나눈다. 토막들의 순서는 구분하며, 길이 $$i$$ 인 토막 하나에 색을 칠하는 방법은 $$g_i$$ 가지가 있다.

길이 $$n$$ 짜리 띠 하나를 (토막으로 나눈 뒤 각 토막을 칠하는) 방법의 수를 $$f(n)$$ 이라 하자. 정의상 $$f(0) = 1$$ 이며 (아무것도 칠하지 않는 한 가지), 첫 번째 토막의 길이가 $$i$$ 인 경우를 기준으로 나누어 세면 다음을 얻는다.

$f(n) = \sum_{i=1}^{n} g_i \cdot f(n-i) \quad (n \ge 1)$

$g_1, g_2, \dots, g_N$ 이 주어질 때, $f(1), f(2), \dots, f(N)$ 을 각각 $$998244353$$ 으로 나눈 나머지를 구하여라.

제약

$1 \le N \le 100{,}000$

$0 \le g_i < 998244353$

입력 형식

첫 줄에 정수 $$N$$ 이 주어진다.

둘째 줄에 $$N$$ 개의 정수 $g_1, g_2, \dots, g_N$ 이 공백으로 구분되어 주어진다. ( $0 \le g_i < 998244353$ )

출력 형식

한 줄에 $f(1), f(2), \dots, f(N)$ 을 각각 $$998244353$$ 으로 나눈 나머지를 공백으로 구분하여 출력한다.

예제 1

입력

4
1 1 1 1

출력

1 2 4 8

설명

모든 $$g_i=1$$ 이면 토막마다 색칠 방법이 한 가지뿐이므로 $$f(n)$$ 은 길이 $$n$$ 짜리 띠를 순서 있는 토막들로 나누는 방법의 수, 즉 $2^{n-1}$ 이다. $$f(1)=1, f(2)=2, f(3)=4, f(4)=8$$ .

예제 2

입력

3
2 0 5

출력

2 4 13

설명

$$g_1=2, g_2=0, g_3=5$$ . $f(1)=g_1\ f(0)=2$ . $f(2)=g_1 f(1)+g_2 f(0)=2\cdot2+0=4$ . $f(3)=g_1 f(2)+g_2 f(1)+g_3 f(0)=2\cdot4+0+5=13$ .

문제 정보

riseoj 작성

출처 Original

태그

자기 자신을 부르는 수열