Connection Status:
Competition Arena > Trisomorphism

Trisomorphism

SRM 728 · 2018-01-24 · by tourist

SRM 728 · 2018-01-24 · by tourist · Advanced Math
Class Name: Trisomorphism
Return Type: int
Method Name: maxSubset
Arg Types: (int)
Problem Statement

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)| = nn.

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.

Notes

  • The number 998244353 is a prime number.

Constraints

  • n will be between 1 and 50, inclusive.
Examples
0)
2
Returns: 4

It's impossible to pick three distinct vertices when n = 2. Thus, no two graphs are trisomophic.

1)
3
Returns: 11
2)
5
Returns: 67
3)
13
Returns: 188742
4)
42
Returns: 441900824

Don't forget about the modulo.

Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Trisomorphism with a public method int maxSubset(int n) · 50 test cases · 2 s / 256 MB per case

Submitting as anonymous