問題一覧 > 通常問題

No.3777 Train Seats

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 34
作問者 : Rapca1256 / テスター : 👑 p-adic aogera tomorunn
お気に入りにしたユーザー ProblemId : 13842 / 自分の提出
問題文最終更新日: 2026-08-22 13:23:05
yukicoder contest 519 (順位表) の他の問題:

問題文

$N$ 個の椅子が横一列に並んでいます。これから、$N$ 人の人が $1$ 人ずつ順番にやってきます。
新しく来た人は、次の条件をすべて満たす椅子が $1$ つ以上あれば、それらのうち $1$ つを選び、座ります。

  • 人が座っていない
  • 右に椅子が存在しないか、右の椅子には人が座っていない
  • 左に椅子が存在しないか、左の椅子には人が座っていない

条件を満たす椅子が存在しない場合は、まだ人が座っていない椅子を $1$ つ選んで座ります。

椅子が座られる順番としてありうるものの総数を $998244353$ で割った余りを求めてください。

入力

$N$

入力は次の制約を満たします。

  • 入力はすべて整数
  • $1 \le N \le 1000$

出力

椅子が座られる順番としてありうるものの総数を $998244353$ で割った余りを求めてください。
最後に改行してください。

サンプル

サンプル1
入力
3
出力
4

左から $i$ 番目の椅子を椅子 $i$ と呼び、$i$ 人目の座る椅子を椅子 $S_i$ としたとき、$S$ の列としては以下が考えられます。

  • $(1, 3, 2)$
  • $(2, 1, 3)$
  • $(2, 3, 1)$
  • $(3, 1, 2)$
サンプル2
入力
1
出力
1

サンプル3
入力
7
出力
1008

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