Universal Cup Judging System

Universal Cup

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

Hitta antalet binära träd (ett binärt träd är ett rotat träd där varje hörn har högst ett vänsterbarn och högst ett högerbarn) med $N$ hörn numrerade $1, 2, \dots, N$ som uppfyller alla följande villkor, och skriv ut resultatet modulo $998244353$.

  • För varje $i = 1, 2, \dots, N$ är preorder-indexet för hörn $i$ lika med $i$. Speciellt är hörn $1$ roten.
  • För varje $i = 1, 2, \dots, M$ är inorder-indexet för hörn $A_i$ lika med $B_i$.

Två binära träd betraktas som olika om det finns ett hörn $v$ sådant att minst ett av följande gäller:

  • Existensen eller hörnnumret för vänsterbarnet till $v$ är annorlunda.
  • Existensen eller hörnnumret för högerbarnet till $v$ är annorlunda.

Preorder-indexet och inorder-indexet för varje hörn $v$ i ett binärt träd definieras som de värden som registreras i preorder[v] respektive inorder[v] när dfs(root) körs i följande pseudokod:

pre_cnt = 1; in_cnt = 1
def dfs(v):
    preorder[v] = pre_cnt; pre_cnt += 1
    if v has a left child:
        dfs(left child of v)
    inorder[v] = in_cnt; in_cnt += 1
    if v has a right child:
        dfs(right child of v)

Indata

Indatan ges i följande format:

$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$

  • Alla indatavärden är heltal.
  • $1 \le M \le N \le 500$
  • $1 \le A_i, B_i \le N$
  • $A_i \ne A_j$ ($i \ne j$)
  • $B_i \ne B_j$ ($i \ne j$)

Utdata

Skriv ut svaret på en enda rad.

Exempel

Indata 1

3 1
2 1

Utdata 1

2

Indata 2

5 3
1 3
2 5
4 2

Utdata 2

0

Indata 3

30 6
12 26
9 5
15 14
19 15
4 2
10 4

Utdata 3

550222816

Förklaring

I det första exemplet finns det exakt två binära träd som uppfyller villkoren. Det ena har hörn $1$ som rot, hörn $2$ som vänsterbarn till hörn $1$ och hörn $3$ som högerbarn till hörn $2$. Det andra har hörn $1$ som rot, hörn $2$ som vänsterbarn till hörn $1$ och hörn $3$ som högerbarn till hörn $1$. Deras preorder- och inorder-index överensstämmer med de givna begränsningarna.

I det andra exemplet uppfyller inget binärt träd villkoren.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1406EditorialOpen题解jianglyView

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.