問題一覧 > 通常問題

No.1356 Split Tile2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 13
作問者 : PCTprobabilityPCTprobability / テスター : KoDKoD blackyukiblackyuki
4 ProblemId : 5751 / 出題時の順位表
問題文最終更新日: 2021-02-01 02:14:36

問題文

$1$ から $N$ の番号がついたタイルが横 $1$ 列に番号 $1,2,...,N$ の順で並んでいます。

PCT 君は、以下の手順に従ってゲームを行うことにしました。

  • 1. 残っているタイルを一つ選び、取り除く。
  • 2. タイルの連結成分の個数が $1$ のとき、ゲームを終了する。そうでないとき、手順 1 にもどる。
ここで、タイル $A$ とタイル $B$ が連結であるとは、$|A - B| = 1$ かつ、タイル $A$ とタイル $B$ が両方残っていることを指します。

ゲームの進み方としてあり得るものは何通りありますか?答えは非常に大きくなることがあるので、 $998244353$ で割ったあまりを求めてください。
$2$ つのゲームの進み方が異なるとは、ある正整数 $i$ について、 $2$ つのゲームで $i$ 番目に取り除いたタイルが異なることを指します。

入力

$N$
  • 入力は全て整数である。
  • $2 \le N \le 10^5$

出力

あり得るゲームの進み方の個数を $998244353$ で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
出力
4

あり得るタイルの取り除き方は、$(1),(2,1),(2,3),(3)$ の $4$ 通りがあります。

サンプル2
入力
2021
出力
597472360

$998244353$ で割った余りを求めてください。

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