/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数列のうち、全ての隣接している 2 項が異なるものを素晴らしい整数列と定めます。
要素の総和が N の素晴らしい整数列全てに対する長さの総和を 998244353 で割ったあまりを求めてください。
制約
- 1 \le N \le 2 \times 10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
8
要素の総和が 4 の素晴らしい整数列は、(4),(1,3),(3,1),(1,2,1) の 4 個です。なので、答えはこれらの長さの総和の 1+2+2+3=8 です。
(2,2) や (1,1,2) は総和が 4 ですが、両方 1 項目と 2 項目が等しいため条件を満たしません。
入力例 2
297
出力例 2
475867236
入力例 3
123456
出力例 3
771773807
Score : 600 points
Problem Statement
A positive-integer sequence is said to be splendid if no two adjacent elements are equal.
Find the sum, modulo 998244353, of the lengths of all splendid sequences whose elements have a sum of N.
Constraints
- 1 \le N \le 2 \times 10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
8
There are four splendid sequences whose sum is 4: (4),(1,3),(3,1),(1,2,1). Thus, the answer is the sum of their lengths: 1+2+2+3=8.
(2,2) and (1,1,2) also have a sum of 4 but ineligible because their 1-st and 2-nd elements are the same.
Sample Input 2
297
Sample Output 2
475867236
Sample Input 3
123456
Sample Output 3
771773807