Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

以下の条件をすべて満たす、$N$ 個の頂点に $1, 2, \dots, N$ の番号が付けられた二分木(二分木とは、各頂点が高々 $1$ つの左の子と高々 $1$ つの右の子を持つ根付き木のことです)の個数を求め、結果を $998244353$ で割った余りを出力してください。

  • 各 $i = 1, 2, \dots, N$ について、頂点 $i$ の行きがけ順(preorder)の番号は $i$ である。特に、頂点 $1$ は根である。
  • 各 $i = 1, 2, \dots, M$ について、頂点 $A_i$ の通りがけ順(inorder)の番号は $B_i$ である。

$2$ つの二分木は、以下の少なくとも一方が成り立つような頂点 $v$ が存在するとき、異なるとみなされます:

  • $v$ の左の子の有無または頂点番号が異なる。
  • $v$ の右の子の有無または頂点番号が異なる。

二分木の各頂点 $v$ の行きがけ順の番号および通りがけ順の番号は、以下の擬似コードにおいて dfs(root) を実行した際に、それぞれ preorder[v] および inorder[v] に記録される値として定義されます:

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)

入力

入力は以下の形式で与えられます:

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

  • 入力される値はすべて整数である。
  • $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$)

出力

答えを $1$ 行で出力してください。

入出力例

入力例 1

3 1
2 1

出力例 1

2

入力例 2

5 3
1 3
2 5
4 2

出力例 2

0

入力例 3

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

出力例 3

550222816

注記

$1$ 番目の例では、条件を満たす二分木はちょうど $2$ つあります。一方は頂点 $1$ を根とし、頂点 $2$ が頂点 $1$ の左の子、頂点 $3$ が頂点 $2$ の右の子である木です。もう一方は頂点 $1$ を根とし、頂点 $2$ が頂点 $1$ の左の子、頂点 $3$ が頂点 $1$ の右の子である木です。これらの行きがけ順および通りがけ順の番号は、与えられた制約と整合しています。

$2$ 番目の例では、条件を満たす二分木は存在しません。

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.