Universal Cup Judging System

Universal Cup

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

Hãy tìm số lượng cây nhị phân (cây nhị phân là một cây có gốc mà trong đó mỗi đỉnh có tối đa một con trái và tối đa một con phải) gồm $N$ đỉnh được đánh số $1, 2, \dots, N$ thỏa mãn tất cả các điều kiện sau, và in ra kết quả theo modulo $998244353$.

  • Với mỗi $i = 1, 2, \dots, N$, chỉ số duyệt tiền thứ tự (preorder index) của đỉnh $i$ là $i$. Đặc biệt, đỉnh $1$ là gốc.
  • Với mỗi $i = 1, 2, \dots, M$, chỉ số duyệt trung thứ tự (inorder index) của đỉnh $A_i$ là $B_i$.

Hai cây nhị phân được coi là khác nhau nếu tồn tại một đỉnh $v$ sao cho ít nhất một trong các điều kiện sau xảy ra:

  • Sự tồn tại hoặc số hiệu đỉnh của con trái của $v$ là khác nhau.
  • Sự tồn tại hoặc số hiệu đỉnh của con phải của $v$ là khác nhau.

Chỉ số duyệt tiền thứ tự và chỉ số duyệt trung thứ tự của mỗi đỉnh $v$ trong cây nhị phân được định nghĩa lần lượt là các giá trị được ghi trong preorder[v] và inorder[v] khi thực thi dfs(root) trong mã giả sau:

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)

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

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

  • Tất cả các giá trị đầu vào đều là số nguyên.
  • $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$)

Kết quả

In ra câu trả lời trên một dòng duy nhất.

Ví dụ

Dữ liệu vào 1

3 1
2 1

Kết quả 1

2

Dữ liệu vào 2

5 3
1 3
2 5
4 2

Kết quả 2

0

Dữ liệu vào 3

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

Kết quả 3

550222816

Giải thích

Trong ví dụ thứ nhất, có đúng hai cây nhị phân thỏa mãn các điều kiện. Một cây có đỉnh $1$ là gốc, đỉnh $2$ là con trái của đỉnh $1$, và đỉnh $3$ là con phải của đỉnh $2$. Cây còn lại có đỉnh $1$ là gốc, đỉnh $2$ là con trái của đỉnh $1$, và đỉnh $3$ là con phải của đỉnh $1$. Các chỉ số duyệt tiền thứ tự và trung thứ tự của chúng đều phù hợp với các ràng buộc đã cho.

Trong ví dụ thứ hai, không có cây nhị phân nào thỏa mãn các điều kiện.

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.