Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Finn antallet binære trær (et binært tre er et rotfestet tre der hver node har høyst ett venstrebarn og høyst ett høyrebarn) med $N$ noder merket $1, 2, \dots, N$ som tilfredsstiller alle følgende betingelser, og skriv ut resultatet modulo $998244353$.

  • For hver $i = 1, 2, \dots, N$ er preorder-indeksen til node $i$ lik $i$. Spesielt er node $1$ roten.
  • For hver $i = 1, 2, \dots, M$ er inorder-indeksen til node $A_i$ lik $B_i$.

To binære trær regnes som forskjellige hvis det finnes en node $v$ slik at minst én av følgende gjelder:

  • Eksistensen eller nodenummeret til venstrebarnet til $v$ er forskjellig.
  • Eksistensen eller nodenummeret til høyrebarnet til $v$ er forskjellig.

Preorder-indeksen og inorder-indeksen til hver node $v$ i et binært tre er definert som verdiene som registreres i henholdsvis preorder[v] og inorder[v] når dfs(root) kjøres i følgende pseudokode:

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)

Inndata

Inndataene gis på følgende format:

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

  • Alle inndataverdier er heltall.
  • $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å én enkelt linje.

Eksempler

Inndata 1

3 1
2 1

Utdata 1

2

Inndata 2

5 3
1 3
2 5
4 2

Utdata 2

0

Inndata 3

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

Utdata 3

550222816

Forklaring

I det første eksempelet er det nøyaktig to binære trær som tilfredsstiller betingelsene. Det ene har node $1$ som rot, node $2$ som venstrebarn til node $1$, og node $3$ som høyrebarn til node $2$. Det andre har node $1$ som rot, node $2$ som venstrebarn til node $1$, og node $3$ som høyrebarn til node $1$. Deres preorder- og inorder-indekser stemmer overens med de gitte begrensningene.

I det andre eksempelet tilfredsstiller ingen binære trær betingelsene.

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.