Universal Cup Judging System

Universal Cup

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

Trouvez le nombre d'arbres binaires (un arbre binaire est un arbre enraciné dans lequel chaque sommet possède au plus un enfant gauche et au plus un enfant droit) à $N$ sommets numérotés $1, 2, \dots, N$ qui satisfont toutes les conditions suivantes, et affichez le résultat modulo $998244353$.

  • Pour chaque $i = 1, 2, \dots, N$, l'indice préfixe (preorder index) du sommet $i$ est $i$. En particulier, le sommet $1$ est la racine.
  • Pour chaque $i = 1, 2, \dots, M$, l'indice infixe (inorder index) du sommet $A_i$ est $B_i$.

Deux arbres binaires sont considérés comme différents s'il existe un sommet $v$ tel qu'au moins l'une des affirmations suivantes soit vraie :

  • L'existence ou le numéro du sommet de l'enfant gauche de $v$ est différent.
  • L'existence ou le numéro du sommet de l'enfant droit de $v$ est différent.

L'indice préfixe et l'indice infixe de chaque sommet $v$ dans un arbre binaire sont définis comme les valeurs enregistrées respectivement dans preorder[v] et inorder[v] lors de l'exécution de dfs(root) dans le pseudocode suivant :

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)

Entrée

L'entrée est donnée sous le format suivant :

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

  • Toutes les valeurs en entrée sont des entiers.
  • $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$)

Sortie

Affichez la réponse sur une seule ligne.

Exemples

Entrée 1

3 1
2 1

Sortie 1

2

Entrée 2

5 3
1 3
2 5
4 2

Sortie 2

0

Entrée 3

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

Sortie 3

550222816

Note

Dans le premier exemple, il existe exactement deux arbres binaires qui satisfont les conditions. L'un a le sommet $1$ comme racine, le sommet $2$ comme enfant gauche du sommet $1$, et le sommet $3$ comme enfant droit du sommet $2$. L'autre a le sommet $1$ comme racine, le sommet $2$ comme enfant gauche du sommet $1$, et le sommet $3$ comme enfant droit du sommet $1$. Leurs indices préfixes et infixes sont cohérents avec les contraintes données.

Dans le deuxième exemple, aucun arbre binaire ne satisfait les conditions.

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.