No.1378 Flattening
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 :
leaf_1415
/ テスター :
IKyopro
タグ : / 解いたユーザー数 40
作問者 :
leaf_1415
/ テスター :
IKyopro
問題文最終更新日: 2020-11-13 14:52:18
問題文
長さ $N$ の正整数の列 $a_1, a_2, \ldots, a_N$ が与えられます。
数列 $a$ には、$1$ から $N$ までの整数がそれぞれちょうど $1$ 回ずつ出現します。
つまり、数列 $a$ は $1, 2, \ldots, N$ の順列です。
数列 $a$ に対して以下の操作を好きな回数（ $0$ 回でもよい）行った結果として得られる可能性のある数列 $a$ が何通りあるかを求めて下さい。
（操作）
-
手順1. $1 \leq i \leq N-1$ を満たす整数 $i$ を選び、$x := \min(a_i, a_{i+1})$ とする。
手順2. $a_i$ と $a_{i+1}$ を $x$ に置き換える。
答えを $998244353$ で割った余りを出力してください。
入力
$N$ $a_1\ a_2\ \cdots\ a_N$
$2 \leq N \leq 5000$
$1 \leq a_i \leq N$
$i \neq j$ ならば $a_i \neq a_j$
入力はすべて整数
出力
答えを $998244353$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 3 1 2
出力
4
初期状態から操作を $1$ 回も行わなければ、$a = (3, 1, 2)$ が得られます。
$i=1$ として操作を行うと、$a = (1, 1, 2)$ が得られます。
そこからさらに $i=2$ として操作を行うと、$a = (1, 1, 1)$ が得られます。
また、初期状態から $i=2$ として操作を行うと、$a = (3, 1, 1)$ が得られます。
作れる数列 $a$ は以上の $4$ 通りとなります。
サンプル2
入力
20 12 16 19 1 17 5 3 18 6 8 14 11 7 10 9 13 15 4 2 20
出力
2708865
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。