#PQJ103x6688. QOJ 103_6688

    ID: 2537 传统题 6000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2009拓扑排序

QOJ 103_6688

IOI2009 中国国家队选拔赛 第二试 2009-05-07 纷繁世界 【问题背景】 这是一个纷繁复杂的世界。 某一天清晨你起床很迟,没有吃上早饭。于是你骑着自行车去超市,但是你 又发现商店的工作人员已经重新贴上了价格标签,零食价格都涨了50%。你一怒 之下就这样饿了一个上午…… 当然,事情也许完全不会这样发展。 某一天清晨你起床比较迟,但还是没有吃上早饭。于是你骑着自行车去超市, 恰好商店的工作人员还没有把涨价后的价格标签贴在零食上。于是你顺利的买了 一些早餐然后逍遥而去…… 或许你会起得更早,也或许商店的工作人员会迟到。 有时候,人们只是按照预想的顺序去完成一些事情,不过可能有一些事件, 它们发生时间的前后顺序会影响世界的发展。 比如,如果商店只有一个西瓜,你想买,我也想买,那么我们买西瓜的先后 顺序就会直接影响到谁最后能够买到西瓜。 这样一个复杂的世界,分析它的运行规律是一件非常重要的工作,也是你所 要研究的。 【问题描述】 简单起见,假定总共有N 个人以及M 种不同类型事件。 定义事件之间的二元关系“相关”:  相关关系是一个二元关系,就是说我们只能定义两种类型的事件间 是否相关;  同一种类型的事件之间一定是相关的;  若事件x 与事件y 是相关的,那么事件y 与事件x 也一定是相关的; 表示第i 个人计划完成的事件序列(称为计划序 令 列),Ci 表示Qi 的长度。Qi 中每个事件Qi,j 都是M 种事件中的某一种,且同一种 类型的事件可以发生多次。 随着时间的推移每个计划序列中的事件都会发生一次且恰好一次;为了简单 起见,不会有任何两个事件发生在同一时刻。 为了描述事件的发生顺序,定义 为世界的一条发展 轨迹,P 是满足如下条件的有序序列:

  1. 对于每个人,计划序列中的每个事件Qi,j 都在P 出现一次且恰好一次;
  2. 对于属于同一个计划序列的两个事件Qi,j1 和Qi,j2(1 ≤ j1 < j2 ≤ Ci),Qi,j1 一定发生在Qi,j2 之前(也就是在P 中位于更靠前的位置); 第2 页 共10 页 IOI2009 中国国家队选拔赛 第二试 2009-05-07 两条轨迹P1 和P2 被定义为本质不同的,当且仅当存在两个相关的事件Qi,j 和Qu,v,他们在P1 和P2 中发生的先后顺序不同,也就是说,如果在P1 中Qi,j 发 生在Qu,v 之前且在P2 中Qi,j 发生在Qu,v 之后,那么P1 和P2 就是本质不同的;如 果在P1 中Qi,j 发生在Qu,v 之后且在P2 中Qi,j 发生在Qu,v 之前,那么P1 和P2 也是 本质不同的; 注意:本质相同具有传递性,即若P1 与P2 本质相同且P2 与P3 本质相同, 那么P1 与P3 一定也本质相同。 【任务】 给定N, M、每个人计划序列以及事件之间的相关关系。你需要计算一共有多 少种本质不同的世界运行轨迹。 【输入文件】 输入文件world.in 第一行包括一个整数,表示人数N。 输入文件第二行包括一个整数,表示事件种类数M,所有类型的事件按照0 至M – 1 编号。 接下来依次给出每个人的计划序列的描述,对于第i 个人: 首先一行一个整数表示序列长度Ci。 第二行包含Ci 个整数,依次给出Qi 中的每个事件Qi,j。 最后M 行输入一个M 行M 列的矩阵dep 用来描述相关关系,每行包含M 个 整数,都是0 或者1。dep(i,j)表示矩阵自上往下的第i 行,自左往右的第j 列所 包含的整数。若dep(i, j)的值为1,那么第i 类事件和第j 类事件就是相关的,否 则这两类事件不相关。 【输出文件】 输出文件world.out 只有一行,一个整数表示本质不同的世界轨迹数T。 【样例输入】 2 3 2 0 1 2 2 1 1 1 0 1 1 1 0 1 1 第3 页 共10 页 IOI2009 中国国家队选拔赛 第二试 2009-05-07 【样例输出】 4 【样例说明】 样例中有2 个人与3 类事件,C1 = C2 = 2。Q1,0 = 0, Q1,1 = 1, Q2,0 = 2, Q2,1 = 1。 一共有4 中不同的发生轨迹: P1 = (Q1,0, Q1,1, Q2,0, Q2,1) P2 = (Q1,0, Q2,0, Q1,1, Q2,1) P3 = (Q1,0, Q2,0, Q2,1, Q1,1) P4 = (Q2,0, Q2,1, Q1,0, Q1,1) 对于其他任何合法的发展轨迹,都一定和这四条轨迹中的某一条本质相同。 例如P = (Q2,0, Q1,0, Q2,1, Q1,1)与P3 是本质相同的,因为两条轨迹只交换了Q1,0 = 0 和Q2,0 = 2 的顺序,但是这两类事件是不相关的。 【数据规模】 总人数N ≤ 10; 事件种类数 M ≤ 15; 计划序列长度Ci ≤ 20; 世界轨迹数T ≤ 106。 第4 页 共10 页