Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Dir ist eine Permutation $P$ von $\{1, 2, \dots, N\}$ gegeben.

Das heißt, $P$ ist ein Array der Länge $N$, das jede ganze Zahl von $1$ bis $N$ genau einmal enthält.

Du kannst die folgende Operation darauf ausführen:

  • Wähle einen Index $i$ ($1 < i < |P|$).
  • Setze $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
  • Lösche $P_{i-1}$ und $P_{i+1}$ aus $P$. Die verbleibenden Elemente werden anschließend neu indiziert, beginnend bei $1$.

Jede solche Operation verringert die Länge von $P$ um $2$. Insbesondere kann diese Operation nicht angewendet werden, wenn die Länge von $P$ gleich $1$ oder $2$ ist.

Bestimme die Anzahl der verschiedenen Arrays, die erreicht werden können, indem diese Operation null- oder mehrmals ausgehend von $P$ ausgeführt wird.

Da dieser Wert groß sein kann, musst du ihn nur modulo $998\,244\,353$ bestimmen.

Eingabe

Die Eingabe erfolgt im folgenden Format:

T
N
P_1 P_2 ... P_N
...

Einschränkungen

  • Alle Eingabewerte sind ganze Zahlen.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le P_i \le N$
  • $P_i \ne P_j$ für alle $i \ne j$.
  • Es wird garantiert, dass die Summe von $N^2$ über alle Testfälle $5000^2$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzige ganze Zahl aus — die Anzahl der verschiedenen Arrays, die durch null- oder mehrmaliges Ausführen der Operation auf $P$ erreicht werden können, modulo $998\,244\,353$.

Beispiel

Eingabe 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

Ausgabe 1

1
2
5
55
365

Hinweis

Testfall 1: Es können keine Operationen ausgeführt werden.

Testfall 2: Es gibt zwei Möglichkeiten:

  • Keine Operationen ausführen. Das endgültige Array ist $[2, 1, 3]$.
  • Eine Operation mit $i = 2$ ausführen. Das endgültige Array ist $[3]$.

Dies sind die einzigen erreichbaren Arrays.

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.