問題一覧 > 通常問題

No.1885 Flat Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : miscalcmiscalc / テスター : 👑 ygussanyygussany ShirotsumeShirotsume
11 ProblemId : 7290 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-04 20:17:49

問題文

整数 $N, X, Y$ が与えられます。$(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ であって、以下の条件をすべて満たすようなものの個数を求めてください。

  • $P_1 = X$
  • $P_N = Y$
  • $|P_{i+1} - P_i| \leq 2$（$1 \leq i \leq N - 1$）
答えは非常に大きくなることがあるので、$998244353$ で割った余りを出力してください。

入力

$N$ $X$ $Y$

  • 入力はすべて整数である
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq X, Y \leq N$
  • $X \neq Y$

出力

条件を満たす $P$ の個数を $998244353$ で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
4 1 4
出力
2

$P = (1, 2, 3, 4), (1, 3, 2, 4)$ の $2$ つが条件を満たします。

サンプル2
入力
6 3 5
出力
1

$P = (3, 1, 2, 4, 6, 5)$ のみが条件を満たします。

サンプル3
入力
4 3 2
出力
0

条件を満たす $P$ は存在しません。

サンプル4
入力
31415 9265 3589
出力
889048175

$998244353$ で割った余りを出力してください。

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