NOI '21 P2 - Intersecting Paths

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem types

There is a directed graph such that the vertices may be partitioned into k levels. The i-th level has n_i vertices, and the number of vertices in level 1 and level k are the same (i.e. n_1 = n_k), and for the j-th level (2 \le j \le k-1), we have n_1 \le n_j \le 2n_1. Edges whose tails are vertices in level j (1 \le j < k) will only go to vertices in level j+1. There are no edges whose heads are vertices in level 1, and there are no edges whose tails are vertices in level k.

Now we want to choose a set of paths with n_1 paths in the set. Each path in the set starts from a vertex in level 1 and ends in a vertex in level k, and a vertex in the graph may only occur in one path. More formally, if we number the vertices in each level by 1, 2, \dots, n_i, then each path may be written as a k-tuple (p_1, p_2, \dots, p_k) denoting that the path passes through vertex p_j (1 \le p_j \le n_j) in level j, and there exists an edge connecting vertex p_j in level j (1 \le j < k) to vertex p_{j+1} in level j+1.

If we draw the paths on paper, we know they will produce some intersections. For paths P,Q, suppose the edges between level j and level j+1 in the paths are (P_j,P_{j+1}) and (Q_j,Q_{j+1}), then if (P_j - Q_j) \times (P_{j+1} - Q_{j+1}) < 0, we say the two paths produce an intersection in level j. The number of intersections of two paths is the sum of number of intersections they produce in level 1, 2, \dots, j-1. For a set of paths, the number of intersections is defined to be sum of number of intersections between two different paths. In the following example, there are 3 paths producing 3 intersections in total. The red dots are the intersections:

Now we want to compute the difference between the number of sets of paths with even number of intersections and the number of sets of paths with odd number of intersections. Two sets of paths are considered to be the same if and only if the k-tuple corresponding to the n_1 paths are the same. Since the final result might be large, please output the answer modulo 998\,244\,353, a prime.

Input Specification

There are multiple test cases in one test set. The first line is an integer T denoting the number of test cases.

For each test case, the first line is an integer k denoting there are k levels of vertices.

The second line contains k integers n_1, n_2, \dots, n_k denoting the number of vertices in each level. It is guaranteed that n_1 = n_k and n_1 \le n_i \le 2n_1 for 2 \le i \le k-1.

The third line contains k-1 integers m_1, m_2, \dots, m_{k-1} denoting the number of edges between vertices in level j and vertices in level j+1. It is guaranteed that m_j \le n_j \times n_{j+1}.

There are k-1 sections of input following. The j-th section (1 \le j < k) contains m_j lines. Each line contains two integers u,v denoting vertex u in level j has an edge whose head is vertex v in level j+1.

It is guaranteed there are no parallel edges.

Output Specification

The output has T lines. Each line contains an integer denoting the answer (the number of sets of paths with even number of intersections minus the number of sets of paths with odd number of intersections) modulo 998\,244\,353.

Sample Input 1

1
3
2 3 2
4 4
1 1
1 2
2 1
2 3
1 2
2 1
3 1
3 2

Sample Output 1

1

Explanation for Sample Output 1

There are two sets of paths with even number of intersections and one with odd number of intersections, so the output is 1.

In set 1, the two paths are (1,1,2) and (2,3,1) in the k-tuple notation. There is one intersection in total. Notice if we swap the two paths, we obtain the same set of paths, and we do not count the same set twice.

In set 2, the two paths are (1,2,1) and (2,1,2). There are 2 intersections.

In set 3, the two paths are (1,2,1) and (2,3,2). There are 0 intersections.

Additional Samples

Sample inputs and outputs can be found here.

Constraints

For all test sets, 2 \le k \le 100, 2 \le n_i \le 100, 1 \le T \le 5. It is guaranteed in each test set there will be at most one test case with n_1 > 10 in each test set.

Test Case k = n_1 \le Additional constraints
1~4 2 10 None.
5~6 10 A,B
7~8 A
9~10 None.
11~13 2 100
14~15 100 A,B
16~17 A
18~20 None.

Additional constraint A: For all i (2 \le i \le k-1), n_i = n_1.
Additional constraint B: There is at most one set of paths.


Comments

There are no comments at the moment.