問題一覧 > 通常問題

No.1378 Flattening

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : leaf_1415leaf_1415 / テスター : 👑 IKyoproIKyopro
4 ProblemId : 5357 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。