問題一覧 > 通常問題

No.1378 Flattening

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 44
作問者 : leaf_1415 / テスター : IKyopro
お気に入りにしたユーザー ProblemId : 5357 / 自分の提出
問題文最終更新日: 2020-11-13 14:52:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 281 (順位表) の他の問題:

Problem Statement

You are given a sequence of positive integers $a_1, a_2, \ldots, a_N$ of length $N$.
Each integer from $1$ to $N$ appears in the sequence $a$ exactly $1$ time.
In other words, the sequence $a$ is a permutation of $1, 2, \ldots, N$.

Find the number of possible sequences $a$ that can be obtained by performing the following operation on the sequence $a$ any number of times (possibly $0$ times).
(Operation)

    Step 1. Choose an integer $i$ satisfying $1 \leq i \leq N-1$, and let $x := \min(a_i, a_{i+1})$.
    Step 2. Replace both $a_i$ and $a_{i+1}$ with $x$.

Print the answer modulo $998244353$.

Input

$N$
$a_1\ a_2\ \cdots\ a_N$

$2 \leq N \leq 5000$
$1 \leq a_i \leq N$
If $i \neq j$, then $a_i \neq a_j$
All inputs are integers

Output

Print the answer modulo $998244353$.
Print a newline at the end.

Sample

Sample 1
Input
3
3 1 2
Output
4

If the operation is not performed even $1$ time from the initial state, $a = (3, 1, 2)$ is obtained.
Performing the operation with $i=1$ gives $a = (1, 1, 2)$.
Further performing the operation with $i=2$ from there gives $a = (1, 1, 1)$.
Also, performing the operation with $i=2$ from the initial state gives $a = (3, 1, 1)$.
The sequences $a$ that can be obtained are the $4$ listed above.

Sample 2
Input
20
12 16 19 1 17 5 3 18 6 8 14 11 7 10 9 13 15 4 2 20
Output
2708865

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