102977: [Atcoder]ABC297 Ex - Diff Adjacent

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

定义一个正整数序列是好的,当且仅当序列中相邻的元素都不相等。你需要求出序列中元素总和为 $n$ 的好序列个数 $\bmod\ 998244353$ 的值。

Output

得分:600分 部分 问题描述 如果一个正整数序列没有相邻的两个元素相等,那么就称该序列是“美妙的”。 找出所有元素和为 N 的美妙序列的长度之和,对 998244353 取模。 部分 约束 * 1≤N≤2×10^5 * 输入中的所有值都是整数。 部分 输入格式 输入通过标准输入给出以下格式: N 部分 输出格式 输出答案。 部分 样例输入 1 4 部分 样例输出 1 8 有四个美妙序列的和为 4:(4)、(1,3)、(3,1)、(1,2,1)。因此,答案是它们长度的和:1+2+2+3=8。 (2,2) 和 (1,1,2) 也有和为 4,但由于它们的第一个和第二个元素相同,所以它们不符合条件。 部分 样例输入 2 297 部分 样例输出 2 475867236 部分 样例输入 3 123456 部分 样例输出 3 771773807

加入题单

上一题 下一题 算法标签: