Universal Cup Judging System

Universal Cup

Limite de temps : 3 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

알려지지 않은 루트 있는 트리의 깊이 우선 탐색(DFS) 순서 $m$개가 주어집니다.

$1$부터 $n$까지 번호가 매겨진 $n$개의 정점을 가지며 정점 $1$이 루트인 루트 있는 트리를 생각합니다. 이 트리는 무방향 연결 그래프이며, 정확히 $n - 1$개의 간선을 가집니다.

DFS의 정의. 고정된 루트 있는 트리에 대해, DFS 순서는 다음과 같이 얻어집니다:

  • 모든 정점은 처음에 방문하지 않은 상태입니다.
  • 루트 $1$에서 시작하여 방문했다고 표시하고 이를 출력합니다.
  • 어떤 정점 $v$에 있을 때, 루트 있는 트리에서 $v$의 모든 자식 정점을 고려합니다. 자식 정점들을 임의의 순서로 선택합니다. 선택된 각 자식 정점 $u$가 아직 방문하지 않은 상태라면, $u$로 이동하여 방문했다고 표시하고 $u$를 출력한 뒤, 같은 방식으로 $u$에서부터 DFS를 계속 진행합니다.

고정된 트리에 대해 각 정점의 자식들을 처리하는 순서의 선택이 달라지면 서로 다른 DFS 순서가 만들어질 수 있습니다. 모든 DFS 순서는 $1, 2, \dots, n$의 순열이며 항상 $1$로 시작합니다.

각각 $1$로 시작하는 $1, 2, \dots, n$의 순열 $m$개가 주어집니다. 이 순열들은 모두 위에서 정의한 의미에서 동일한 루트 있는 트리(루트는 $1$)의 DFS 순서임이 알려져 있습니다(서로 다른 DFS 실행마다 자식 순서의 선택은 다를 수 있습니다).

여러분의 과제는 이 $m$개의 DFS 순서를 모두 만들어낼 수 있는 서로 다른 루트 있는 트리가 몇 개인지 구하는 것입니다.

두 루트 있는 트리는 간선 집합이 다를 때 서로 다른 것으로 간주합니다.

답이 매우 클 수 있으므로, $10^9 + 7$로 나눈 나머지를 출력해야 합니다.

입력

첫 번째 줄에 두 정수 $n$과 $m$($1 \le n, m \le 500$)이 주어집니다.

다음 $m$개의 줄에는 각각 $k$번째 DFS 순서를 설명하는 정수 $1, 2, \dots, n$의 순열 $p_{k,1}, p_{k,2}, \dots, p_{k,n}$이 주어집니다.

모든 $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.