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

Sinulle annetaan joukon $\{1, 2, \dots, N\}$ permutaatio $P$.

Toisin sanoen $P$ on pituuden $N$ taulukko, joka sisältää jokaisen kokonaisluvun väliltä $1$ – $N$ täsmälleen kerran.

Voit suorittaa sille seuraavan operaation:

  • Valitse indeksi $i$ ($1 < i < |P|$).
  • Aseta $P_i = \max(P_{i-1}, P_i, P_{i+1})$.
  • Poista $P_{i-1}$ ja $P_{i+1}$ taulukosta $P$. Jäljelle jäävät alkiot indeksoidaan sen jälkeen uudelleen alkaen luvusta $1$.

Jokainen tällainen operaatio vähentää taulukon $P$ pituutta luvulla $2$. Erityisesti, jos taulukon $P$ pituus on $1$ tai $2$, tätä operaatiota ei voida käyttää.

Etsi erilaisten taulukoiden lukumäärä, jotka voidaan saavuttaa suorittamalla tämä operaatio nolla kertaa tai useammin lähtien taulukosta $P$.

Koska tämä arvo voi olla suuri, sinun tarvitsee vain laskea se modulo $998\,244\,353$.

Syöte

Syöte annetaan seuraavassa muodossa:

T
N
P_1 P_2 ... P_N
...

Rajoitukset

  • Kaikki syötearvot ovat kokonaislukuja.
  • $1 \le T \le 10^5$
  • $1 \le N \le 5000$
  • $1 \le P_i \le N$
  • $P_i \ne P_j$ kaikilla $i \ne j$.
  • On taattu, että arvojen $N^2$ summa yli kaikkien testitapausten ei ylitä arvoa $5000^2$.

Tuloste

Tulosta jokaista testitapausta kohden yksi kokonaisluku — erilaisten taulukoiden lukumäärä, jotka voidaan saavuttaa suorittamalla operaatio nolla kertaa tai useammin taulukolle $P$, modulo $998\,244\,353$.

Esimerkki

Syöte 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

Tuloste 1

1
2
5
55
365

Huomautus

Testitapaus 1: Operaatioita ei voida suorittaa lainkaan.

Testitapaus 2: Mahdollisuuksia on kaksi:

  • Älä suorita yhtään operaatiota. Lopullinen taulukko on $[2, 1, 3]$.
  • Suorita yksi operaatio arvolla $i = 2$. Lopullinen taulukko on $[3]$.

Nämä ovat ainoat saavutettavissa olevat taulukot.

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.