P4099 [HEOI2013]SAO

    • 193通过
    • 397提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 前缀和 动态规划,动规,dp 后缀数组,SA 拓扑排序 枚举,暴力 各省省选 2013 河北
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG, 含有 n 个关卡。但是,挑战不同关卡的顺序是一个很大的问题。

    有 n – 1 个对于挑战关卡的限制,诸如第 i 个关卡必须在第 j 个关卡前挑战, 或者完成了第 k 个关卡才能挑战第 l 个关卡。并且,如果不考虑限制的方向性, 那么在这 n – 1 个限制的情况下,任何两个关卡都存在某种程度的关联性。即, 我们不能把所有关卡分成两个非空且不相交的子集,使得这两个子集之间没有任 何限制。

    输入输出格式

    输入格式:

    第一行,一个整数 T,表示数据组数。

    对于每组数据,第一行一个整数 n,表示关卡数。接下来 n – 1 行,每行为 “i sign j”,其中 0 ≤ i, j ≤ n – 1 且 i ≠ j,sign 为“<”或者“>”,表示第 i 个关卡 必须在第 j 个关卡前/后完成。

    输出格式:

    对于每个数据,输出一行一个整数,为攻克关卡的顺序方案个数,mod 1,000,000,007 输出。

    输入输出样例

    输入样例#1: 复制
    2 
    5 
    0 < 2 
    1 < 2 
    2 < 3 
    2 < 4 
    4 
    0 < 1 
    0 < 2 
    0 < 3
    输出样例#1: 复制
    4 
    6

    说明

    对于 20%的数据有 n ≤ 10。

    对于 40%的数据有 n ≤ 100。

    对于另外 20%的数据有,保证数据中 sign 只会是<,并且 i < j。

    对于 100%的数据有 T ≤ 5,1 ≤ n ≤ 1000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。