자기 자신을 부르는 수열
다이아몬드 II의견: 0
길이가 \(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\)으로 나눈 나머지를 공백으로 구분하여 출력한다.
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\).
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
평가 및 의견
자기 자신을 부르는 수열
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
자기 자신을 부르는 수열