Universal Cup Judging System

Universal Cup

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

Сізге $\{1, 2, \dots, N\}$ жиынының $P$ орын алмастыруы берілген.

Яғни, $P$ — $1$-ден $N$-ге дейінгі әрбір бүтін санды дәл бір рет қамтитын ұзындығы $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.