Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

給你一個 $\{1, 2, \dots, N\}$ 的排列 $P$。

也就是說,$P$ 是一個長度為 $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$ 開始。

每次此類操作都會使 $P$ 的長度減少 $2$。特別地,如果 $P$ 的長度為 $1$ 或 $2$,則無法進行此操作。

求從 $P$ 開始,透過執行零次或多次該操作可以達到的不同陣列的數量。

由於該值可能很大,你只需要求出其對 $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$ 執行零次或多次操作可以達到的不同陣列的數量,對 $998\,244\,353$ 取模。

範例

輸入範例 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:無法進行任何操作。

測試用例 2:有兩種可能性:

  • 不進行任何操作。最終陣列為 $[2, 1, 3]$。
  • 對 $i = 2$ 進行一次操作。最終陣列為 $[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.