P4489 [CTSC2009] A Complicated World

This is a complex and intricate world. One morning you woke up late and missed breakfast. You rode your bike to the supermarket, only to find that the staff had already put up new price tags and all snacks had gone up by $50\%$. In anger, you stayed hungry the whole morning. Of course, things might not have turned out that way. Another morning you woke up a bit late and still missed breakfast. You rode your bike to the supermarket, and it happened that the staff had not yet put up the new price tags. You smoothly bought some breakfast and went on your way. Perhaps you would get up earlier, or perhaps the store staff would arrive late. Sometimes people complete tasks in an expected order, but for some events, the relative order in which they occur can influence how the world develops. For example, if the store has only one watermelon, and both you and I want to buy it, then the order in which we try to buy it will directly determine who gets it. Analyzing the rules of operation in such a complicated world is very important, and that is exactly what you are going to study.

For simplicity, assume there are $N$ people and $M$ types of events. Define a binary relation “related” between event types: - The relation is binary, meaning we only determine whether two types of events are related. - Events of the same type are always related. - If event $x$ is related to event $y$, then event $y$ is also related to event $x$. Let $Q_i = (Q_{i, 1}, Q_{i, 2}, \cdots, Q_{i, C_i})$ be the sequence of events person $i$ plans to complete (called the plan sequence), where $C_i$ is the length of $Q_i$. Each event $Q_{i, j}$ is one of the $M$ event types, and events of the same type may occur multiple times. As time goes by, each event in every plan sequence will occur exactly once, and no two events occur at the same moment. To describe the order in which events occur, define $P = (Q_{i_1, j_1}, Q_{i_2, j_2}, \cdots, Q_{i_l, j_l})$ as a development trajectory of the world. $P$ is an ordered sequence satisfying: 1. For every person, each event $Q_{i, j}$ in their plan sequence appears in $P$ exactly once. 2. For any two events $Q_{i, j_1}$ and $Q_{i, j_2}$ belonging to the same plan sequence ($1 \leq j_1 < j_2 \leq C_i$), $Q_{i, j_1}$ must occur before $Q_{i, j_2}$ (i.e., appear earlier in $P$). Two trajectories $P_1$ and $P_2$ are defined to be essentially different if and only if there exist two related events $Q_{i, j}$ and $Q_{u, v}$ whose relative order differs in $P_1$ and $P_2$. In other words, if in $P_1$ the event $Q_{i, j}$ occurs before $Q_{u, v}$ while in $P_2$ the event $Q_{i, j}$ occurs after $Q_{u, v}$, then $P_1$ and $P_2$ are essentially different; similarly, if in $P_1$ $Q_{i, j}$ occurs after $Q_{u, v}$ but in $P_2$ it occurs before $Q_{u, v}$, then $P_1$ and $P_2$ are also essentially different. Note: “Essentially the same” is transitive. That is, if $P_1$ is essentially the same as $P_2$, and $P_2$ is essentially the same as $P_3$, then $P_1$ is necessarily essentially the same as $P_3$. Given $N$, $M$, each person’s plan sequence, and the relatedness between event types, compute how many essentially different world development trajectories there are.

- The first line contains an integer denoting the number of people $N$. - The second line contains an integer denoting the number of event types $M$. All event types are numbered from $0$ to $M - 1$. - Then, for each person $i$, the description of their plan sequence is given: - The first line contains one integer, the sequence length $C_i$. - The second line contains $C_i$ integers, giving each event $Q_{i, j}$ in $Q_i$ in order. - Finally, $M$ lines follow, containing an $M \times M$ matrix dep that describes the relatedness. Each line contains $M$ integers, each being $0$ or $1$. dep(i, j) denotes the integer in the $i$-th row (from top to bottom) and the $j$-th column (from left to right). If dep(i, j) equals $1$, then event type $i$ and event type $j$ are related; otherwise, they are unrelated.

Output a single line containing one integer, the number $T$ of essentially different world trajectories.

Sample Explanation There are $2$ people and $3$ event types, with $C_1 = C_2 = 2$. $Q_{1,0} = 0$, $Q_{1,1} = 1$, $Q_{2,0} = 2$, $Q_{2,1} = 1$. There are $4$ different development trajectories: - $P_1 = (Q_{1,0}, Q_{1,1}, Q_{2,0}, Q_{2,1})$; - $P_2 = (Q_{1,0}, Q_{2,0}, Q_{1,1}, Q_{2,1})$; - $P_3 = (Q_{1,0}, Q_{2,0}, Q_{2,1}, Q_{1,1})$; - $P_4 = (Q_{2,0}, Q_{2,1}, Q_{1,0}, Q_{1,1})$. Any other valid development trajectory is necessarily essentially the same as one of these four. For example, $P = (Q_{2,0}, Q_{1,0}, Q_{2,1}, Q_{1,1})$ is essentially the same as $P_3$, because the two trajectories only swap the order of $Q_{1,0} = 0$ and $Q_{2,0} = 2$, and those two event types are unrelated. Constraints For $100\%$ of the testdata: $N \leq 10$, $M \leq 15$, $C_i \leq 20$, $T \leq 10^6$. Translated by ChatGPT 5