Universal Cup Judging System

Universal Cup

時間限制: 3 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

تُعطى لك $m$ من ترتيبات البحث في العمق أولاً (DFS) لشجرة مجذّرة غير معروفة.

نعتبر الأشجار المجذّرة التي تحتوي على $n$ من الرؤوس المرقمة من $1$ إلى $n$، حيث الرأس $1$ هو الجذر. الشجرة غير موجهة ومترابطة، ولها بالضبط $n - 1$ من الأضلاع.

تعريف DFS. بالنسبة لشجرة مجذّرة ثابتة، يتم الحصول على ترتيب DFS كما يلي:

  • جميع الرؤوس غير مزورة في البداية.
  • ابدأ عند الجذر $1$، وعلّمه كمزور واطبعه.
  • عندما تكون عند رأس ما $v$، خذ بعين الاعتبار جميع أبناء $v$ في الشجرة المجذّرة. اختر أبناءه بـ أي ترتيب. لكل ابن مختار $u$ لا يزال غير مزور، انتقل إلى $u$، وعلّمه كمزور، واطبع $u$، وتابع DFS من $u$ بنفس الطريقة.

بالنسبة لشجرة ثابتة، قد تؤدي الاختيارات المختلفة للترتيب الذي تتم به معالجة أبناء كل رأس إلى إنتاج ترتيبات DFS مختلفة. جميع ترتيبات DFS هي تبديلات للأعداد $1, 2, \dots, n$ وتبدأ دائماً بالعدد $1$.

تُعطى لك $m$ من التبديلات للأعداد $1, 2, \dots, n$، يبدأ كل منها بالعدد $1$. ويُقال لك إن كلاً منها هو ترتيب DFS لـ نفس الشجرة المجذّرة (ذات الجذر $1$) بالمعنى المحدد أعلاه (ربما باستخدام اختيارات مختلفة لترتيب الأبناء في عمليات تشغيل DFS المختلفة).

مهمتك هي تحديد عدد الأشجار المجذّرة المختلفة التي يمكن أن تنتج جميع ترتيبات DFS الـ $m$ هذه.

تُعتبر شجرتان مجذّرتان مختلفتين إذا كانت مجموعتا أضلاعهما مختلفتين.

نظراً لأن الإجابة قد تكون كبيرة جداً، يجب عليك طباعتها بباقي القسمة على $10^9 + 7$.

الإدخال

يحتوي السطر الأول على عددين صحيحين $n$ و $m$ ($1 \le n, m \le 500$).

يحتوي كل سطر من الأسطر الـ $m$ التالية على تبديل $p_{k,1}, p_{k,2}, \dots, p_{k,n}$ للأعداد الصحيحة $1, 2, \dots, n$، يصف ترتيب DFS رقم $k$.

لكل $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.