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