Problem Statement | | | Note: This problem has a nonstandard time limit: 4 seconds.
You are given an undirected graph G1.
This graph has k vertices, numbered 0 through k-1.
You are given the int k.
You are also given two equally-long int[]s a and b that describe the edges of G1.
For each i, there is an edge between a[i] and b[i].
Finally, you are given an int n.
Construct a new graph G2 as follows.
- Take n distinct copies of G1. We will call them "copy 0" through "copy n-1".
- For each i, in copy i, increment the numbers of all vertices by i*k. After this change, the vertices in our graph have distinct numbers from 0 to (k*n-1).
- Take the complement of the graph you currently have. I.e., a pair of vertices is connected by an edge after this step if and only if it wasn't connected before this step.
A Hamiltonian path in G2 is a path that visits each vertex of G2 exactly once.
The path may start and end in any vertex of G2.
The first and the last vertex of the path do not have to be connected by an edge.
Two paths differ if their sequences of visited vertices differ.
In particular, the path (0,1,2,3) differs from the path (3,2,1,0).
Count the number of Hamiltonian paths in G2.
Return that count modulo 998244353 (a prime number).
| | | Definition | | | | Class: | HamiltonianPaths | | Method: | countPaths | | Parameters: | int, int[], int[], int | | Returns: | int | | Method signature: | int countPaths(int k, int[] a, int[] b, int n) | | (be sure your method is public) |
| | | | | | Constraints | | - | k will be between 1 and 14, inclusive. | | - | a will have between 0 and k*(k-1)/2 elements, inclusive. | | - | b will have exactly the same number of elements as a. | | - | The graph described by the edges a,b will not have any self-loops or multiple edges. | | - | n will be between 1 and 50,000, inclusive. | | | Examples | | 0) | | | | | Returns: 152 | Our graph G1 looks as follows:
0 - 1 - 2
When constructing G2, we start by taking two copies of G1 and relabeling them:
0 - 1 - 2
3 - 4 - 5
Finally, we take the complement of this graph.
The result looks as follows:
-----
| |
0 1 2
|\/|\/|
|/\|/\|
3 4 5
| |
-----
The resulting graph does also contain the edges 0-5 and 2-3, these are not shown in the figure above.
Some examples of Hamiltonian paths in this graph:
- 0-2-5-3-1-4
- 4-1-3-5-2-0
- 0-2-4-1-3-5
- 0-3-1-4-2-5
- 0-5-2-3-1-4
|
|
| | 1) | | | | | Returns: 129246395 | | The final graph will be a complete graph with 12*10000 nodes. So, the answer in this case is (120000)! mod 998244353 = 129246395. |
|
| | 2) | | | | | | 3) | | | | | Returns: 1 | | The resulting graph G2 has a single isolated vertex 0.
There is exactly one Hamiltonian path: the path that starts in vertex 0 and ends immediately. |
|
| | 4) | | | | 4 | {1,2,3,2,3,3} | {0,0,0,1,1,2} | 1 |
| Returns: 0 | |
| | 5) | | | | 4 | {1,2,3,2,3,3} | {0,0,0,1,1,2} | 10006 |
| Returns: 33330626 | |
| | 6) | | | | 14 | {0,4,0,0,0,12,2,2,9,2,2,3,3,3,3,4,8,4,5,5,10,11,6,12,10,13,10,13,12,13,11} | {2,0,5,8,11,1,5,6,2,10,12,4,5,9,13,7,4,13,6,7,5,5,8,7,8,8,9,9,10,10,13} | 50000 |
| Returns: 372837676 | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
|
