Universal Cup Judging System

Universal Cup

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

給定一棵未知有根樹的 $m$ 個深度優先搜尋(DFS)序。

我們考慮包含 $n$ 個頂點(編號從 $1$ 到 $n$)的有根樹,其中頂點 $1$ 是根。該樹是無向連通的,並且恰好有 $n - 1$ 條邊。

DFS 的定義。 對於一棵固定的有根樹,其 DFS 序透過以下方式獲得:

  • 所有頂點初始時均為未造訪狀態。
  • 從根節點 $1$ 開始,將其標記為已造訪並輸出它。
  • 當你位於某個頂點 $v$ 時,考慮該有根樹中 $v$ 的所有子節點。以任意順序選擇它的子節點。對於每個選定的且仍未造訪的子節點 $u$,移動到 $u$,將其標記為已造訪,輸出 $u$,並以相同的方式從 $u$ 繼續進行 DFS。

對於一棵固定的樹,處理每個頂點子節點的不同順序可能會產生不同的 DFS 序。所有的 DFS 序都是 $1, 2, \dots, n$ 的排列,並且總是以 $1$ 開頭。

給定 $m$ 個 $1, 2, \dots, n$ 的排列,每個排列都以 $1$ 開頭。已知它們都是同一棵有根樹(以 $1$ 為根)在上述定義意義下的 DFS 序(在不同的 DFS 過程中可能使用了不同的子節點順序)。

你的任務是確定有多少棵不同的有根樹可以產生所有這 $m$ 個 DFS 序。

如果兩棵有根樹的邊集不同,則認為它們是不同的。

由於答案可能非常大,你應該輸出其對 $10^9 + 7$ 取模後的結果。

輸入格式

第一行包含兩個整數 $n$ 和 $m$($1 \le n, m \le 500$)。

接下來的 $m$ 行,每行包含一個整數 $1, 2, \dots, n$ 的排列 $p_{k,1}, p_{k,2}, \dots, p_{k,n}$,描述第 $k$ 個 DFS 序。

對於每個 $k$,所有的 $p_{k,i}$ 互不相同,且 $p_{k,1} = 1$。

輸出格式

輸出一個整數:頂點集為 $1, 2, \dots, n$ 且以 $1$ 為根的有根樹的數量,使得每一個給定的序列都是該樹的合法 DFS 序,結果對 $10^9 + 7$ 取模。

範例

3 2
1 2 3
1 3 2
1
4 1
1 2 3 4
5
5 2
1 2 3 4 5
1 2 4 3 5
3

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.