Trisomorphism | Topcoder Archive

Problem Statement

Let S(n) be the set of directed graphs with n vertices labeled from 0 to n-1 such that there is exactly one outgoing edge from each vertex. Self-loops are allowed. Therefore, we have |S(n)| = nⁿ.

Given such a graph, a twirl is an operation that takes three distinct vertices labeled A, B, C and relabels them B, C, A. For example, if you choose the vertices labeled 4, 2, and 77, the following three things will happen simultaneously:

The label of the first chosen vertex will change from 4 to 2.
The label of the second chosen vertex will change from 2 to 77.
The label of the third chosen vertex will change from 77 to 4.

Two graphs are called trisomorphic if we can transform one into the other by performing a sequence of zero or more twirls.

You are given an int n. Find the size of the maximum subset of S(n) such that no two graphs in this subset are trisomorphic. Return this size modulo 998244353.

Definition

Class:: Trisomorphism
Method:: maxSubset
Parameters:: int
Returns:: int
Method signature:: int maxSubset(int n)
(be sure your method is public)

Notes

The number 998244353 is a prime number.

Constraints

n will be between 1 and 50, inclusive.

Examples

```
2
```
```
Returns: 4
```
It's impossible to pick three distinct vertices when n = 2. Thus, no two graphs are trisomophic.
```
3
```
```
Returns: 11
```
```
5
```
```
Returns: 67
```
```
13
```
```
Returns: 188742
```
```
42
```
```
Returns: 441900824
```
Don't forget about the modulo.

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.