Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

$\{1, 2, \dots, N\}$ の順列 $P$ が与えられます。

つまり、$P$ は $1$ から $N$ までの各整数をちょうど 1 回ずつ含む長さ $N$ の配列です。

これに対して以下の操作を行うことができます:

  • インデックス $i$($1 < i < |P|$)を選ぶ。
  • $P_i = \max(P_{i-1}, P_i, P_{i+1})$ と設定する。
  • $P$ から $P_{i-1}$ と $P_{i+1}$ を削除する。残った要素は $1$ から始まるようにインデックスが振り直される。

このような操作を 1 回行うごとに、$P$ の長さは $2$ 減少します。特に、$P$ の長さが $1$ または $2$ の場合、この操作は適用できません。

$P$ から始めてこの操作を 0 回以上行うことで到達できる異なる配列の個数を求めてください。

この値は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを求めてください。

入力

入力は以下の形式で与えられます:

T
N
P_1 P_2 ... P_N
...

制約

  • 入力値はすべて整数である。
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le P_i \le N$
  • すべての $i \ne j$ について $P_i \ne P_j$。
  • すべてのテストケースにおける $N^2$ の総和は $5000^2$ を超えないことが保証される。

出力

各テストケースについて、$P$ に対して操作を 0 回以上行うことで到達できる異なる配列の個数を $998\,244\,353$ で割った余りを 1 つの整数として出力せよ。

入出力例

入力例 1

5
2
2 1
3
2 1 3
5
3 1 4 5 2
10
1 2 3 4 5 6 7 8 9 10
15
5 7 6 12 2 13 10 1 11 4 3 9 14 15 8

出力例 1

1
2
5
55
365

注記

テストケース 1: 操作を 1 回も行うことができません。

テストケース 2: 以下の 2 通りの可能性があります:

  • 操作を行わない。最終的な配列は $[2, 1, 3]$ である。
  • $i = 2$ として操作を 1 回行う。最終的な配列は $[3]$ である。

到達可能な配列はこれらのみです。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.