問題一覧 > 通常問題

No.1356 Split Tile2

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : PCTprobability / テスター : KoD blackyuki
お気に入りにしたユーザー ProblemId : 5751 / 自分の提出
問題文最終更新日: 2021-10-14 23:04:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘中入試コンテストday2 (順位表) の他の問題:

Problem Statement

Tiles numbered from $1$ to $N$ are lined up in $1$ horizontal row in the order $1,2,...,N$.

PCT has decided to play a game according to the following procedure.

  • 1. Choose one remaining tile and remove it.
  • 2. If the number of connected components of tiles is $1$, end the game. Otherwise, go back to step 1.

Here, tile $A$ and tile $B$ are connected if $|A - B| = 1$ and both tile $A$ and tile $B$ remain.

How many possible ways can the game proceed? Since the answer can be very large, find it modulo $998244353$.

$2$ ways the game proceeds are considered different if, for some positive integer $i$, the tiles removed $i$-th in the $2$ games are different.

Input

$N$
  • All inputs are integers.
  • $2 \le N \le 10^5$

Output

Output the number of possible ways the game can proceed, modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
3
Output
4

The possible ways to remove the tiles are the following $4$: $(1),(2,1),(2,3),(3)$.

Sample 2
Input
2021
Output
597472360

Find the remainder when divided by $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。