No.1356 Split Tile2
タグ : / 解いたユーザー数 20
作問者 :
PCTprobability
/ テスター :
KoD
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もしくは右上の雲マークをクリックしてアカウントを作成してください。