Statistics

Problem Statement for "Trisomorphism"

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.

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

  1. 2

    Returns: 4

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

  2. 3

    Returns: 11

  3. 5

    Returns: 67

  4. 13

    Returns: 188742

  5. 42

    Returns: 441900824

    Don't forget about the modulo.

  6. 1

    Returns: 1

  7. 4

    Returns: 28

  8. 6

    Returns: 175

  9. 7

    Returns: 454

  10. 8

    Returns: 1227

  11. 9

    Returns: 3281

  12. 10

    Returns: 8936

  13. 11

    Returns: 24508

  14. 12

    Returns: 67909

  15. 14

    Returns: 528123

  16. 15

    Returns: 1484116

  17. 16

    Returns: 4188913

  18. 17

    Returns: 11862010

  19. 18

    Returns: 33702530

  20. 19

    Returns: 96021326

  21. 20

    Returns: 274274951

  22. 21

    Returns: 785177942

  23. 22

    Returns: 255861624

  24. 23

    Returns: 483315537

  25. 24

    Returns: 663653653

  26. 25

    Returns: 805189296

  27. 26

    Returns: 320839602

  28. 27

    Returns: 904809730

  29. 28

    Returns: 856997678

  30. 29

    Returns: 890909494

  31. 30

    Returns: 653194069

  32. 31

    Returns: 992733388

  33. 32

    Returns: 210032541

  34. 33

    Returns: 992705617

  35. 34

    Returns: 686723910

  36. 35

    Returns: 357938868

  37. 36

    Returns: 364964412

  38. 37

    Returns: 651649626

  39. 38

    Returns: 574425112

  40. 39

    Returns: 266182583

  41. 40

    Returns: 177310497

  42. 41

    Returns: 124780056

  43. 43

    Returns: 645025037

  44. 44

    Returns: 617422487

  45. 45

    Returns: 8554626

  46. 46

    Returns: 196654294

  47. 47

    Returns: 961051825

  48. 48

    Returns: 317309493

  49. 49

    Returns: 24040314

  50. 50

    Returns: 449689257

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.
This problem was used for: