Universal Cup Judging System

Universal Cup

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

נתונה לך תמורה $P$ של $\{1, 2, \dots, N\}$.

כלומר, $P$ הוא מערך באורך $N$ המכיל כל מספר שלם מ-$1$ עד $N$ בדיוק פעם אחת.

באפשרותך לבצע עליו את הפעולה הבאה:

  • בחר אינדקס $i$ ($1 < i < |P|$).
  • הצב $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
  • מחק את $P_{i-1}$ ואת $P_{i+1}$ מתוך $P$. האיברים הנותרים ממוספרים מחדש החל מ-$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$
  • $P_i \ne P_j$ לכל $i \ne 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.